Standard merge sort
Merge sorting works by breaking an array into two halves, over and over again, until the size of each half is below some threshold. For a threshold of 2 this means simply swapping the two items in that part of the array if they are out of order. For a larger threshold you could use an insertion sort or something. Once we have sorted two halves of the array, we have to merge them together to arrive at the final sorted array.
MergeSort(array, range)
if (range.length == 2)
if (array[range.start] > array[range.end]) Swap(array[range.start], array[range.end])
else if (range.length > 2)
mid = range.start + range.length/2
MergeSort(array, MakeRange(range.start, mid))
MergeSort(array, MakeRange(mid, range.end))
Merge(array, MakeRange(range.start, mid), MakeRange(mid, range.end))
Standard merge
The merge operation of the merge sort algorithm takes two arrays that are already sorted (either from swapping or insertion sorting, as mentioned above), and combines them into a single array containing A and B sorted together. The operation is acutally quite simple: just take the smaller of the two values at the start of A and B and add it to the final array. Once A and B are empty, the final array is completed!
Merge(array, A, B)
Copy A and B into a buffer
A_count = 0, B_count = 0, insert = 0
while (A_count < A.length && B_count < B.length)
if (buffer[A_count] <= buffer[B.start + B_count])
array[A.start + insert] = buffer[A_count]
A_count = A_count + 1
else
array[A.start + insert] = buffer[B.start + B_count]
B_count = B_count + 1
insert = insert + 1
Copy the remaining part of the buffer back into the array
Here's an example of how it works:
1. we want to merge these two arrays, A and B:
[0 2 4 7] [1 3 7 8] []
2. 0 is smaller
[0 2 4 7] [1 3 7 8] []
^ ^
3. 1 is smaller
[2 4 7] [1 3 7 8] [0]
^ ^
4. 2 is smaller
[2 4 7] [3 7 8] [0 1]
^ ^
5. 3 is smaller
[4 7] [3 7 8] [0 1 2]
^ ^
6. 4 is smaller
[4 7] [7 8] [0 1 2 3]
^ ^
7. 7 and 7 are equal, so give precedence to A
[7] [7 8] [0 1 2 3 4]
^ ^
8. A is empty, so just add the rest of B to the end
[] [7 8] [0 1 2 3 4 7]
^
9. A + B have been merged!
[] [] [0 1 2 3 4 7 7 8]
Problems
There are some significant drawbacks to this design, especially if you're concerned about memory usage. The recursion actually uses O(log n) stack space, and the merge operation requires a separate buffer that's the same size as the original array.
Can we do better? Of course!
Merge sort without recursion
To remove the recursion, we can use what's called a [bottom-up merge sort] (http://www.algorithmist.com/index.php/Merge_sort#Bottom-up_merge_sort). Here's what it looks like for an array of a size that happens to be a power of two:
MergeSort(array, count)
for (length = 1; length < count; length = length * 2)
for (merge = 0; merge < count; merge = merge + length * 2)
start = merge
mid = merge + length
end = merge + length * 2
Merge(array, MakeRange(start, mid), MakeRange(mid, end))
For an array of size 16, it does this (the operation is shown to the right):
[ 15 2 13 7 3 0 11 4 12 6 10 14 1 9 8 5 ]
merge 0-0 and 1-1 [[15][2 ] 13 7 3 0 11 4 12 6 10 14 1 9 8 5 ]
merge 2-2 and 3-3 [ 2 15 [13][7 ] 3 0 11 4 12 6 10 14 1 9 8 5 ]
merge 4-4 and 5-5 [ 2 15 7 13 [3 ][0 ] 11 4 12 6 10 14 1 9 8 5 ]
merge 6-6 and 7-7 [ 2 15 7 13 0 3 [11][4 ] 12 6 10 14 1 9 8 5 ]
merge 8-8 and 9-9 [ 2 15 7 13 0 3 4 11 [12][6 ] 10 14 1 9 8 5 ]
merge 10-10 and 11-11 [ 2 15 7 13 0 3 4 11 6 12 [10][14] 1 9 8 5 ]
merge 12-12 and 13-13 [ 2 15 7 13 0 3 4 11 6 12 10 14 [1 ][9 ] 8 5 ]
merge 14-14 and 15-15 [ 2 15 7 13 0 3 4 11 6 12 10 14 1 9 [8 ][5 ]]
merge 0-1 and 2-3 [[2 15][7 13] 0 3 4 11 6 12 10 14 1 9 5 8 ]
merge 4-5 and 6-7 [ 2 7 13 15 [0 3 ][4 11] 6 12 10 14 1 9 5 8 ]
merge 8-9 and 10-11 [ 2 7 13 15 0 3 4 11 [6 12][10 14] 1 9 5 8 ]
merge 12-13 and 14-15 [ 2 7 13 15 0 3 4 11 6 10 12 14 [1 9 ][5 8 ]]
merge 0-3 and 4-7 [[2 7 13 15][0 3 4 11] 6 10 12 14 1 5 8 9 ]
merge 8-11 and 12-15 [ 0 2 3 4 7 11 13 15 [6 10 12 14][1 5 8 9 ]]
merge 0-7 and 8-15 [[0 2 3 4 7 11 13 15][1 5 6 8 9 10 12 14]]
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ]
Which is of course exactly what we wanted. Note that it starts off by merging chunks of size 1, then size 2, then size 4, and finally size 8.
To extend this logic to non-power-of-two sizes, we floor the size down to the nearest power of two for these calculations, then scale back again to get the ranges to merge.
MergeSort(array, count)
> power_of_two = FloorPowerOfTwo(count)
> scale = count/power_of_two // 1.0 <= scale < 2.0
for (length = 16; length < power_of_two; length = length * 2)
for (merge = 0; merge < power_of_two; merge = merge + length * 2)
start = merge * scale
mid = (merge + length) * scale
end = (merge + length * 2) * scale
Merge(array, MakeRange(start, mid), MakeRange(mid, end))
The floating-point multiplication was verified as correct for over 17 billion items (as in there was no unexpected roundoff error), but if that seems a bit flaky to you it's also possible to handle the scaling with integer operations:
MergeSort(array, count)
power_of_two = FloorPowerOfTwo(count)
fractional_base = power_of_two/16
fractional_step = size % fractional_base (modulus, which gets the remainder from size/fractional_base)
decimal_step = floor(size/fractional_base)
for (length = 16; length < power_of_two; length = length * 2)
decimal = fractional = 0
while (decimal < size)
start = decimal
decimal = decimal + decimal_step
fractional = fractional + fractional_step
if (fractional >= fractional_base)
fractional = fractional - fractional_base
decimal = decimal + 1
mid = decimal
decimal = decimal + decimal_step
fractional = fractional + fractional_step
if (fractional >= fractional_base)
fractional = fractional - fractional_base
decimal = decimal + 1
end = decimal
Merge(array, MakeRange(start, mid), MakeRange(mid, end))
decimal_step = decimal_step * 2
fractional_step = fractional_step * 2
if (fractional_step >= fractional_base)
fractional_step = fractional_step - fractional_base
decimal_step = decimal_step + 1
This is considerably more involved than the standard bottom-up design, but it guarantees that the two ranges being merged will always have the same size to within one item, which ends up being about 10% faster.
This removes the need for the O(log n) stack space! Although, to be fair, that wasn't really an issue – sorting 1.5 million items only recurses ~20 times anyway. The real problem is that O(n) space for the separate buffer! What can we do about that?
Merging using a half-size buffer
One simple optimization is to only copy the values from A into the buffer, since by the time we run the risk of overwriting values in the range of B we will have already read and compared those values. Here's what this variant looks like:
Merge(array, A, B)
Copy the values from A into the buffer, but leave B where it is
A_count = 0, B_count = 0, insert = 0
while (A_count < A.length && B_count < B.length)
if (buffer[A_count] <= array[B.start + B_count])
array[A.start + insert] = buffer[A_count]
A_count = A_count + 1
else
array[A.start + insert] = array[B.start + B_count]
B_count = B_count + 1
insert = insert + 1
Copy the remaining part of the buffer back into the array
Merging without overwriting the contents of the half-size buffer
Finally, if instead of assigning values we swap them to and from the buffer, we end up with a merge operation that still requires extra space, but doesn't overwrite any of the values that were stored in that extra space:
Merge(array, A, B)
Block swap the values in A with those in the buffer
A_count = 0, B_count = 0, insert = 0
while (A_count < A.length && B_count < B.length)
if (buffer[A_count] <= array[B.start + B_count])
Swap(array[A.start + insert], buffer[A_count])
A_count = A_count + 1
else
Swap(array[A.start + insert], array[B.start + B_count])
B_count = B_count + 1
insert = insert + 1
Block swap the remaining part of the buffer with the remaining part of the array
The items in the buffer will likely be in a different order afterwards, but at least they're still there.
So now we can efficiently merge A and B without losing any buffer values, but we still need that additional buffer to exist. There isn't much we can do about that... but what if this extra buffer was part of the original array?
That's the idea behind [in-place merging] (https://github.com/BonzaiThePenguin/WikiSort/blob/master/Chapter%203.%20In-Place.md)!