How does a merge sort work?

Merge sort follows the divide and conquer approach. This is also a comparison based sorting algorithm like Bubble sort, selection sort and insertion sort etc.

In this method we divide the array into two halves. We recursively sort these two parts and merge them into single array. Here the base case for recursion is just one element i.e no need to sort an array with just one element.

For example let us consider an array of 5 elements
[3,2,1,5,4]

It is divided into two sub-arrays [3,2,1] and [5,4]. We apply merge sort recursively on both the sub-arrays and merge them to become a single sorted array.

Here is how the first sub-array gets sorted.
[3,2,1] is divided into [3,2] and [1]. No need sort the second sub-array because it just contains one element.
[3,2] is divided into [3], [2].

The merge procedure combines the arrays [3], [2] into sorted sub-array [2,3].

Then the sub-array [2,3] is merged with [1] to become [1,2,3]

Finally [1,2,3] gets merged with [4,5] to become [1,2,3,4,5] which is fully sorted.

The merge procedure works as follows. The input to the merge procedure is two sorted sub-arrays. 

We initialize two pointers to the first elements of two sub-arrays. We copy the lesser element among them to a temporary array and advance the corresponding pointer to the next element. We repeat this procedure until atleast one of the sub-arrays becomes empty.

Finally we copy the non-empty sub-array elements to the temporary array.

Here is the Java implementation of merge sort. 

public class Main {
public static void main(String[] args)
{
int [] array = {51,126,98,12,3,34,269,73,6,88};
mergeSort( array, 0, array.length-1);
for( int i = 0; i < array.length; i++)
{
System.out.print(array[i] + " ");
}
}
public static void mergeSort(int[] array, int left, int right )
{
if( left < right)// If the array has at least one element
{
int mid = (left + right) / 2;
mergeSort(array, left, mid);
mergeSort(array, mid+1, right);
merge(array, left, mid+1, right);
}
}
public static void merge(int [] array, int l, int m, int r)
{
//We need a temporary array of size r-l+1 for the merged elements
int [] temp = new int[r-l+1];
int i = l; //index of first sub-array
int j = m; //index of second sub array
int k = 0;
while( i < m && j <= r)
{
if( array[i] < array[j])
{
temp[k++] = array[i++];
}
else
{
temp[k++] = array[j++];
}
}
//copy if there are any elements remaining in any half
while( i < m )
{
temp[k++] = array[i++];
}
while ( j <= r )
{
temp[k++] = array[j++];
}
//copy sorted elements from temp to original array
for( i = l,j=0 ; i <= r; i++,j++)
{
array[i] = temp[j];
}
}

} 
 
 

This code runs in O(n log n) time in the worst case also. But it is not an in-place sorting mechanism because we use a temporary array in the merge procedure.