Merge Sort - Sorting Algorithms

Merge sort is a divide and conquer algorithm where we divide the given array into two halves and then merge them assuming that the divided sub arrays are sorted.

In merge sort we keep dividing the array and its subarrays until there is only one element left in the subarray and an array with only one element is always sorted.

After an array is divided into two halves we use the merge function to merge both array in such a way that the merged array is sorted.

Thus there are two methods used one is used to divide the array and another one is used to merge the divided array. The real magic for array sorting happens in the merge method.

Let’s try to understand the the Merge sort with the help of an example -

Suppose we want to sort an array in ascending order - {12, 1,11,4,3,2,44,5,455,76,87,43,45, 55}

Step 1. Dividing into two halves or almost two halves -

Length of the array is 14 so we can divide it into two subarrays having 7 elements each.
{12, 1,11,4,3,2,44} and {5,455,76,87,43,45, 55}

Now these two subarrays can be divided further into two halves, because we cannot merge them until they are sorted.

So we will keep dividing them until we have subarray which has only one element because an array with one element is always sorted.
Now we can start merging the subarrays because now they are sorted.

Step 2. Merging the sorted sub arrays -

To merge the elements of two sorted arrays we will compare the corresponding elements of both the arrays and choose the smaller element and put it in the merged array.
Once all the elements of any one of the arrays are exhausted , we will then simply insert all the remaining elements of the another array in the merged array if there are any elements left in the sub array

Example -
Suppose we have two sorted subarrays - {1,22 33,41} - {7,66,89,90}

Compare 1 with 7, since 1< 7 put 7 in the merged array Merged array - 1

Compare 22 with 7, since 7 < 22 , put 7 in the merged array Merged array - 1, 7

Compare 22 with 66, since 22 < 66 , put 22 in the merged array Merged array - 1, 7, 22

And so on..

Let’s write a Java program for Merge Sort using Recursion :

package algo.sorting;

public class MergeSort {

public static void main(String args[]) {
  int[] arr = new int[] { 12, 1, 11, 4, 3, 2, 44, 5, 455, 76, 87, 43, 45,
    55 };
  
  System.out.println("Unsorted Array - ");
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
  
  System.out.println();
  System.out.println("Sorted Array after Merge Sort - ");
  sort(arr, 0, arr.length - 1);

  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
 }

 public static void sort(int[] arr, int l, int r) {

  if (l < r) {
   // int m = l + (r-l)/2;
   int m = (l + r) / 2;

   sort(arr, l, m);
   sort(arr, m + 1, r);

   merge(arr, l, m, r);
  }
 }

 public static void merge(int[] arr, int l, int m, int r) {
  int n1 = m - l + 1;
  int n2 = r - m;

  int left[] = new int[n1];
  int right[] = new int[n2];

  for (int i = 0; i < n1; i++) {
   left[i] = arr[l + i];
  }

  for (int i = 0; i < n2; i++) {
   right[i] = arr[m + 1 + i];
  }

  int i = 0;
  int j = 0;
  int k = l;
  while (i < n1 && j < n2) {
   if (left[i] < right[j]) {
    arr[k] = left[i];
    i++;
   } else {
    arr[k] = right[j];
    j++;
   }
   k++;
  }

  while (i < n1) {
   arr[k] = left[i];
   i++;
   k++;
  }
  while (j < n2) {
   arr[k] = right[j];
   j++;
   k++;
  }
 } 
 
}

Unsorted Array - 
12 1 11 4 3 2 44 5 455 76 87 43 45 55 
Sorted Array after Merge Sort - 
1 2 3 4 5 11 12 43 44 45 55 76 87 455