Thursday, February 13, 2020

Merge Sort In Java

Merge sort

Merge sort algorithm is a divide and conquers approach based algorithm, with time complexity of n log(n) order, quicksort. An input array passed to sort using merge sort is divided into two equal parts until they are divided into small enough arrays that can be sorted and merged. In Merge sort java program there are two methods merge(), and sort(). merge() method merges two sorted arrays into one sorted array. sort() method first divides the input array into the smallest arrays possible that can be merged and calls the merge method() to merge arrays in sorted order. sort() method is recursive in nature. Merge sort can be applied with the help of recursion very easily.

Merge Sort Algorithm

//Input is an array of numbers and left and right bound to apply to sort within

merge_Sort(arr[], left, right)

If right > left
1. Find the middle point to divide the array into two halves: 
                         Middle element mid = (left+right)/2
2. Call merge_Sort for left half: 
                        Call mergeSort(arr, left, mid)
3. Call merge_Sort for right half:
                        Call mergeSort(arr, mid, right)
4. Merge the two halves sorted in step 2 and 3:
                       Call merge(arr, left, mid, right)

// merge is another method to merge two sorted arrays

Java merge sort
Merge Sort Algorithm(Sequence of execution)

Merge Sort Program

 public class MergeSortExample {
//merge sort
      void merge(int arr[],int left,int mid,int right)
      {
            int ls=mid-left+1;
            int rs=right-mid;
            //create arrays
            int left_arr[]=new int[ls];
            int right_arr[]=new int[rs];
            //copy
            for(int i=0;i<ls;i++)
            {
                  left_arr[i]=arr[left+i];
            }
            for(int j=0;j<rs;j++)
            {
                  right_arr[j]=arr[mid+1+j];
            }
            //merge
            int i=0;
            int j=0;
            int k=left;
            while(i<ls && j<rs)
            {
                  if(left_arr[i]<right_arr[j])
                  {
                        arr[k]=left_arr[i];
                        i++;
                  }
                  else
                  {
                        arr[k]=right_arr[j];
                        j++;
                  }
                  k++;
            }
            //merge remaining
            while(i<ls)
            {
                  arr[k]=left_arr[i];
                  i++;
                  k++;
            }
            while(j<rs)
            {
                  arr[k]=right_arr[j];
                  j++;
                  k++;
            }
            //merge complete
      }
      //create sort method
      void sort(int arr[],int l,int r)
      {
            if(r>l)
            {
                  int mid=(r+l)/2;
                  sort(arr,l,mid);
                  sort(arr,mid+1,r);
                  merge(arr, l, mid, r);
            }
      }
      public static void main(String[] args) {
            //test
            int arr[]= {7,1,13,15,16,45,12,6,11,33};
            System.out.println("Array before sorting");
            for(int i:arr)
                  System.out.print(i+"\t");
            System.out.print();
            MergeSortExample mse=new MergeSortExample();
            mse.sort(arr, 0, arr.length-1);
            System.out.println("Array after sorting");
            for(int i:arr)
                  System.out.print(i+"\t");
      }
}
Output:
Array before sorting
7     1     13    15    16    45    12    6     11    33   
Array after sorting
1     6     7     11    12    13    15    16    33    45   Out

Video Tutorial