Merge Sort

Intro

Merge sort is an efficient divide-and-conquer sorting algorithm that has a time complexity of O(n log n).

A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems, until they become simple enough to be solved directly.

Merge sort - how does it work?

In Merge sort, we split the input array into two parts, and then split each part into two and do the same for all parts until we get the parts with only one element. We consider those sub-arrays as sorted since we don't have more than one element. 

After that, we start merging the parts together, and that is the point when we perform sorting. 

For example, we have an array that has an element [5], and another array that has an element [3]. 

When we merge them together, we get one array of 2 elements [3,5] which is sorted.

We perform all these steps recursively. 

Here is one illustration of the merge sort:

So we split the array of 8 elements into 8 arrays of 1 element. Then we begin with merging until we get the final sorted array.

Let's code it

Below is the Java implementation of the Merge sort. We use recursion since we need to perform the same steps for every part of the array.

The main part is the merging. This is the method that takes two merged arrays and combines them into one.

public static void merge(int[] arr, int[] leftArr, int[] rightArr, int left, int right) {
int i = 0, j = 0, k = 0;

// iterate over the left and right array, compare elements and place them in order inside // the arr array
while (i < left && j < right) {
if (leftArr[i] <= rightArr[j]) {

arr[k++] = leftArr[i++];

}
else {
arr[k++] = rightArr[j++];

}
}

//We need to iterate separately the left and right arrays in case there are some leftovers,

// which can easily happen, and put all the remaining elements inside the arr array

// Note, There will be always leftovers from only one of the arrays, not both.
while (i < left) {
arr[k++] = leftArr[i++];

}

while (j < right) {
arr[k++] = rightArr[j++];

}
}

So here, we compare the elements from the leftArr and rightArr, and if the element from the leftArr is less or equal to the element from rightArr, we put it into arr, which is the original array.
And we increment the i, so that we compare the next element from the leftArr with the same element from the rightArr.
Only when we find the element that is smaller or equal to the element from the other array, we increment the counter (i or j) so that we can move to the next element, while the element from the other array is still used for comparing.

Here is the actual method that performs the Merge sort:

public void mergeSort(int[] arr, int n) {
if (n < 2) {
return;
}
int mid = n / 2;
int[] leftArr = new int[mid];
int[] rightArr = new int[n - mid];

for (int i = 0; i < mid; i++) {
leftArr[i] = arr[i];

}

for (int i = mid; i < n; i++) {
rightArr[i - mid] = arr[i];

}
mergeSort(leftArr, mid);

mergeSort(rightArr, n - mid);

merge(arr, leftArr, rightArr, mid, n - mid);

}

Here, the base case is if the n is less than 2. If yes, it means we got to the array that has only one element and we don't want to continue. 

If no, we find the middle of the array, and we split it by creating two new arrays and populating them with the elements from both sides of the original array.

Then we call the recursive method mergeSort providing the left and the right arrays.
The same steps are being performed, first on the left array, until we get two arrays with the size of 1, and then we go back a step and start working on all the right parts, performing the same steps recursively.

At the end, we call the merge method to merge the arrays into one. With that, we are actually populating/overriding the elements from the original array with sorted elements.

Here is the complete code:

public class MergeSort {

public void mergeSort(int[] arr, int n) {
if (n < 2) {
return;
}
int mid = n / 2;
int[] leftArr = new int[mid];
int[] rightArr = new int[n - mid];

for (int i = 0; i < mid; i++) {
leftArr[i] = arr[i];
}

for (int i = mid; i < n; i++) {
rightArr[i - mid] = arr[i];
}
mergeSort(leftArr, mid);
mergeSort(rightArr, n - mid);

merge(arr, leftArr, rightArr, mid, n - mid);
}

public static void merge(int[] a, int[] leftArr, int[] rightArr, int left, int right) {
int i = 0, j = 0, k = 0;

while (i < left && j < right) {
if (leftArr[i] <= rightArr[j]) {
a[k++] = leftArr[i++];
} else {
a[k++] = rightArr[j++];
}
}

while (i < left) {
a[k++] = leftArr[i++];
}

while (j < right) {
a[k++] = rightArr[j++];
}
}
}

Merge sort - analysis

Merge sort in all cases - worst, average, and best has a time complexity of O(n log n) as it always divides the array into two halves and takes linear time to merge two halves.

Let's see what does O(n log n) mean and why Merge sort has it?

Let's start with the merge method. The merge method takes in two arrays, iterate over them, compares the elements, and puts them sorted in the array that is also passed in.

Since the maximum number of iterations in all loops is n, where n is equal the to length of the array, then we know that the time complexity of the merge method is O(n).

Now, what about the mergeSort method? 

Let's see one more illustration of what merge sort does to an array:

As you can see, by diving the array and then by diving each part further, we got something that looks like a binary tree.

At each level of the binary tree, the number of calls to the merge function doubles but the merge time is halved, so the merge performs a total of n iterations per level.
If the merge requires n iterations per level, and we know that binary trees will have log2 n + 1 levels, we see that the total number of iterations is N(log2 n + 1).

Note: When the list of input size n is divided into two halves, we get the log n time complexity.

That’s why the Merge sort’s time complexity is O(n log n).

Space complexity is O(n) since we are creating a new array, so we need extra memory space to sort the input array. 

Merge sort is a stable algorithm.