Chapter 2: Merging
==================

**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)!
