Merge sort java

Hey guys!! Welcome to flower brackets blog. Today in this post you will learn merge sort java.

merge sort java

Merge sort is comparison based sorting algorithm which sorts array in ascending order. Like quicksort, merge sort is also divide and conquer algorithm.

Also read – bubble sort java program

In merge sort, given array is divided into two smaller portions, calling itself (recursive call) then merging two smaller portions. Let’s learn merge sort with an example.

So let’s say we want to sort a small list of integers 20, 40, 30 and 10.

merge sort java

One way to sort them would be to recursively divide the list into two smaller lists. Now 20 and 40 is already sorted, but 30 and 10 have to swap places. After swapping we have 20, 40, 10 and 30.

The leftmost number is the smallest number in above two smaller list. So we compare 20 to 10. 10 is smaller so we will add 10 to the main list first and then we compare the remaining integers.

Also read – how to sort hashmap by values in java

20 is the smaller so we add 20 to the main list. Then we compare 30 and 40, 30 is the smaller number so we add 30 to main list.

Now all we have left is 40. So we add that too to the main list. Now we have a sorted list of four integers. That in a nutshell is how merge sort works.

Below is the java program for merge sort,

public class JavaMergeSort
{ 
   void sorting(int num[], int left, int main, int right)
   {
      // finding size of two sub arrays 
      int list1 = main - left + 1; 
      int list2 = right - main; 

      // creating temporary array
      int L[] = new int[list1]; 
      int R[] = new int[list2]; 

      // copying data to temporary array
      for(int a = 0; a < list1; ++a) 
         L[a] = num[left + a]; 
      for(int b = 0; b < list2; ++b) 
         R[b] = num[main + 1+ b]; 

      // existing index of first and second sub array 
      int p = 0, q = 0; 

      // existing index of merged sub array 
      int r = left; 
      while(p < list1 && q < list2) 
      { 
         if(L[p] <= R[q]) 
         { 
            num[r] = L[p]; 
            p++; 
         } 
         else
         { 
            num[r] = R[q]; 
            q++; 
         } 
         r++; 
      } 

      // copying remaining elements of L[] array
      while(p < list1) 
      { 
         num[r] = L[p]; 
         p++; 
         r++; 
      } 

      // copying remaining elements of R[] array
      while(q < list2) 
      { 
         num[r] = R[q]; 
         q++; 
         r++; 
      }
   }

   // function that sorts
   void sort(int arrNum[], int l, int r) 
   { 
      if(l < r) 
      { 
         // finding middle point 
         int m = (l + r) / 2; 

         // sorting first and second list 
         sort(arrNum, l, m); 
         sort(arrNum , m+1, r); 

         // merging sorted list 
         sorting(arrNum, l, m, r); 
      } 
   } 

   // display array
   static void displayArray(int arr[]) 
   { 
      int number = arr.length; 
      for(int a = 0; a < number; ++a) 
         System.out.print(arr[a] + " "); 
      System.out.println(); 
   }

   public static void main(String[] args) 
   {
      int arrNumbers[] = {33, 00, 55, 11, 22, 44};
      System.out.println("Before sorting - "); 
      displayArray(arrNumbers); 

      JavaMergeSort obj = new JavaMergeSort(); 
      obj.sort(arrNumbers, 0, arrNumbers.length - 1); 

      System.out.println("\nAfter sorting - "); 
      displayArray(arrNumbers);
   }
}

Output :

merge sort java

Before sorting –
33 00 55 11 22 44

After sorting –
0 11 22 33 44 55


Time and space complexity of merge sort

Time complexity of merge sort is O(n log n) can be expressed as recurrence relation,

T(n) = 2T(n/2) + O(n)

Space : O(n)

Related Posts