Merge sort in java

Let’s learn merge sort in java.

Merge sort in java

Merge sort is divide and conquer algorithm. In merge sort, given array is divided into two smaller portions. To divide a collection, take the middle of collection and split into two smaller lists.

These two smaller portions are again recursively splitted till they are broken into single element. Let’s learn merge sort algorithm java with example. So let’s say we want to sort a small list of integers 20, 40, 30 and 10.

One way to sort them would be to recursively divide the list into two smaller lists. 20, 40 and 30, 10. 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 and 10. 10 is smaller so we will add 10 to the main list first and then we compare the remaining integers.

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. Here’s merge sort program in java.

Java implementation

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:

Before sorting –
33 00 55 11 22 44

After sorting –
0 11 22 33 44 55

Merge sort time complexity

Time complexity of merge sort has O(n log n) in best case, average case of O(n log n) and worst case of O(n log n) can be expressed as recurrence relation.

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

Space complexity: O(n)

Also read – garbage collection in java