Overview
Merge Sort is a divide and conquer algorithm. First we divide the array into two parts (left and right) using the middle index of the array to be sorted. Then we sort each part separately and finally combine the parts together in order. Merge sort uses more space compared to Quick Sort as we need to divide the array and store them in separate variables, although there are some implementations of merge sort that use constant space
Pseudo Code
- Find middle index of the array (length of array / 2)
- Create two arrays left (0 to middle index) and right (middle index to last index)
- Sort each part individually
- Note: An array is sorted if there is only one element in the array so we can use this as the base condition for recursion
- Merge two sorted parts together
Visualization
The following image from wikipedia will help us visualize the pseudo code
As we can see in the image above first we keep dividing the array into two halves (left and right) till there is only one element in each individual array. At this point we know that all the individual arrays are sorted as there is only one element in each of them. Next we merge the arrays in order till we get the final sorted array.
Implementation
public class MergeSortBlog {
public static void main(String[] args) {
int[] sampleArray = { 423, 99, 1, 5, 2, 7, 8, 9, 11, 3, 5 };
mergeSort(sampleArray);
System.out.println(Arrays.toString(sampleArray));
}
//Merge Sort algorithm - recursive
private static void mergeSort(int[] array) {
//base condition for recursion
//array is sorted if there is one or less elements in the array
if (array.length <= 1)
return;
//find middle index of the array
var middle = array.length / 2;
//divide arrays into two parts
int[] left = new int[middle];
int[] right = new int[array.length - middle];
for (int i = 0; i < left.length; i++)
left[i] = array[i];
for (int i = 0; i < right.length; i++)
right[i] = array[middle + i];
//sort left and right part
mergeSort(left);
mergeSort(right);
//merge the array
mergeArrays(array, left, right);
}
//Merge the left and right array
private static void mergeArrays(int[] array, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j])
array[k++] = left[i++];
else
array[k++] = right[j++];
}
while (i < left.length)
array[k++] = left[i++];
while (j < right.length)
array[k++] = right[j++];
}
}
Runtime Complexity
- Time Complexity: O(n log n)
- Dividing O(log n) – we are halving the array on each recursion
- Merging O(n)
- therefore the total complexity is O(n log n)
- Space complexity: O(n) – we need extra space to store the two parts