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.
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.
public class MergeSort {
public static void main(String[] args) {
int []testArray = {5, 0, 1, 6, 3, 4};
mergeSort(testArray);
for(int v: testArray) {
System.out.print(v + " ");
}
}
private static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2)
return ;
mergeSort(arr, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int low, int high) {
if (low >= high)
return;
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
private static void merge(int[] arr, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int leftIndex = low, rightIndex = mid + 1, resultIndex = 0;
while (leftIndex <= mid && rightIndex <= high) {
if (arr[leftIndex] <= arr[rightIndex]) {
temp[resultIndex++] = arr[leftIndex];
leftIndex++;
} else {
temp[resultIndex++] = arr[rightIndex];
rightIndex++;
}
}
while (leftIndex <= mid) {
temp[resultIndex++] = arr[leftIndex++];
}
while (rightIndex <= high) {
temp[resultIndex++] = arr[rightIndex++];
}
System.arraycopy(temp, 0, arr, low, temp.length);
}
}