In the previous section, we tried to divide the array in such a way that when we sort each part, the entire array is sorted. We faced the problem that when we try to do that, the two parts are not equal in size causing the algorithm to sometimes take a quadratic amount of time. What if, instead of trying to divide the array in a way that sorting the parts would sort the whole, we just divide the array into two equal halves? Of course then, sorting the parts will not sort the entire array. However, if we have two array parts sorted on their own, can we merge them together to produce a sorted array as a whole? If we can do this efficiently enough, we would have an algorithm guaranteed to be efficient. As it turns out, it is possible. But we need to think about where the merged array will be stored. Since the values are being copied from the source array, the result needs to be stored in a separate place. So, we will need another storage of equal size for mergesort.
.
Merge of sorted arrays
The preceding figure shows a part of the merging operation. We keep the current position of each of the arrays. In each step, we compare the values in the current positions in both the input sorted arrays.
We copy whichever of them is smaller to the target location and increment the corresponding current position. We keep doing this until we finish one of the arrays, after which the elements of the other array can just be copied over. The following shows the code for the merge operation. One thing to note is that, since the merge will be used for a mergesort, it presumes both the input arrays to be the same array with different indexes and the target arrays to have the same size. The source has three indexes: start, mid, and end. It is assumed that the source parts are residing side by side in the source array. The variable start points to the start of the first part. The integer mid stores the index of the start of the second part and also acts as the end of the first part, as the parts are contiguous. Finally, the end variable stores the end of the second array:
private static <E> void merge(E[] array, int start, int mid, int end, E[] targetArray, Comparator<E> comparator) {
int i = start;
int j = mid;
int k = start;
while (k < end) {The first two cases are for the time when one of the source arrays has been exhausted:
if (i == mid) {
targetArray[k] = array[j];
j++;
} else if (j == end) {
targetArray[k] = array[i];
i++;
} If none of the arrays are exhausted, copy from the correct array:
else if (comparator.compare(array[i], array[j]) > 0) {
targetArray[k] = array[j];
j++;
} else {
targetArray[k] = array[i];
i++;
}Finally, the target location must also be incremented:
k++;
}
}With this merge function available to us, we can now proceed to do the mergesort. It involves the following steps:
- Divide the array into two equal parts.
- Mergesort the parts.
- Merge the sorted parts into a full sorted array.
Of course, we do not need to do anything for an array with zero or one element. So, that will be our exit case:
public static <E> void mergeSort(E[] sourceArray, int start,
int end, E[] tempArray, Comparator<E> comparator) {Just return to the calling function for an array of zero or one element. This is our base case:
if (start >= end - 1) {
return;
}For any array of size bigger than 1, divide the array into two halves–start to mid and mid to end. Then merge-sort them separately, and then merge the two sorted subarrays to a combined sorted array in tempArray, which is an auxiliary space that we are using:
int mid = (start + end) / 2;
mergeSort(sourceArray, start, mid, tempArray, comparator);
mergeSort(sourceArray, mid, end, tempArray, comparator);
merge(sourceArray, start, mid, end, tempArray, comparator);Finally, copy the contents of tempArray to sourceArray so that the source is now sorted:
System.arraycopy(tempArray, start, sourceArray, start,
end - start);
}Let's start from the complexity of the merge operation. The merge operation is not recursive. In every step, it increments either i or j. When both these variables reach the end of the respective arrays, the merge ends. The comparison happens at most once per any of these increments. This means that there are at most as many comparisons as there are elements in both the sub-arrays combined. The copying of the contents of tempArray to sourceArray also, of course, takes operations proportional to the number of elements in tempArray, which is the same as the number of elements in the sourceArray. So, the number of operations in each step is proportional to n, apart from the recursive call. The recursive call works on both parts of the array, which are themselves half the size of the entire array. Thus, if T(n) is the time taken, we have the following:
T(n) = 2T(n/2) + an + b
Here, a and b are constants.
This is the same equation as the one obtained for the typical case of the quicksort algorithm, and we know that the solution gives us T(n) = θ(n lg n). This is the estimate for the both the average case and the worst case because, in both cases, the array will always be divided into two equal halves irrespective of the contents of the array. In fact, the worst case is when all the copying also requires a comparison, which is the case we considered.
In the best case, one of the arrays will have all its elements copied before even the first element of the second array is copied, thus requiring only half as many comparisons. But this case gives the same complexity of T(n) = θ(n lg n). So, irrespective of the actual contents of the array we started with, mergesort will always have the same asymptotic complexity.
In our rather simplistic example, we first merged the subarrays into tempArray, and then we copied it back to sourceArray. Can the copying be avoided? Can we use tempArray itself as the result of the merge? It turns out that we can. In this case, both sourceArray and tempArray would be used rather symmetrically, the only difference being that sourceArray holds the original input array. Otherwise, they are two pre-allocated arrays of the same size. However, the code will get a little more complicated.
Let us first consider what would happen if we do not copy the contents of tempArray to sourceArray and try to use tempArray itself as the content of the sorted array. Then, in each step, sourceArray and tempArray would need to be swapped, that is, tempArray would become sourceArray and vice versa. Since in each step, tempArray and sourceArray are getting swapped, the actual array that holds the result depends on whether the number of steps required to sort the array is odd or even.
Now, if the array we started with had a number of elements equal to an exact integral power of 2, the source array could always be divided into two sub-arrays of the exact same size. This means, the number of steps required to sort each of these sub-arrays would be exactly the same. This means that the actual array that holds the sorted result would be the same after sorting either sub-array. However, in reality, the number of elements in the array is not an exact power of 2 most of the time, and hence, one sub-array is a little bigger than the other. This results in a different number of steps being required to sort either sub-array, causing them to potentially store the resultant sorted array in different arrays. We have to consider these cases as well. So, when the result of sorting either sub-array is stored in the same array, we store the output of the merge in the other array. If not, we always store the output of the merge in the array that holds the result of sorting the second part of the array.
First, we change the merge function to handle two different arrays holding the contents of two different inputs:
private static <E> void merge(E[] arrayL, E[] arrayR,
int start, int mid, int end, E[] targetArray,
Comparator<E> comparator) {
int i = start;
int j = mid;
int k = start;
while (k < end) {
if (i == mid) {
targetArray[k] = arrayR[j];
j++;
} else if (j == end) {
targetArray[k] = arrayL[i];
i++;
} else if (comparator.compare(arrayL[i], arrayR[j]) > 0) {
targetArray[k] = arrayR[j];
j++;
} else {
targetArray[k] = arrayL[i];
i++;
}
k++;
}
}With this merge function available, we write our efficient mergesort in the following way. Note that we need some way to inform the calling function about which pre-allocated array contains the result, so we return that array:
public static <E> E[] mergeSortNoCopy(E[] sourceArray, int start,
int end, E[] tempArray, Comparator<E> comparator) {
if (start >= end - 1) {
return sourceArray;
}First, split and merge-sort the sub-arrays as usual:
int mid = (start + end) / 2;
E[] sortedPart1 =
mergeSortNoCopy(sourceArray, start, mid, tempArray,
comparator);
E[] sortedPart2 =
mergeSortNoCopy(sourceArray, mid, end, tempArray,
comparator);If both the sorted sub-arrays are stored in the same pre-allocated array, use the other pre-allocated array to store the result of the merge:
if (sortedPart2 == sortedPart1) {
if (sortedPart1 == sourceArray) {
merge(sortedPart1, sortedPart2, start, mid, end,
tempArray, comparator);
return tempArray;
} else {
merge(sortedPart1, sortedPart2, start, mid, end,
sourceArray, comparator);
return sourceArray;
}
} else {In this case, we store the result in sortedPart2 because it has the first portion empty:
merge(sortedPart1, sortedPart2, start, mid, end,
sortedPart2, comparator);
return sortedPart2;
}
}Now we can use this mergesort as follows:
Integer[] anotherArray = new Integer[array.length]; array = mergeSortNoCopy(array, 0, array.length, anotherArray, (a, b)->a-b); System.out.println(Arrays.toString(array));
Here is the output:
[1, 1, 1, 2, 2, 3, 3, 4, 5, 10, 24, 30, 33, 35, 35, 53, 67, 78]
Note that this time, we had to ensure that we use the output returned by the method as, in some cases, anotherArray may contain the final sorted values. The efficient no-copy version of the mergesort does not have any asymptotic performance improvement, but it improves the time by a constant. This is something worth doing.