Merge Sort — A Practical Sort

One of the first algorithms on a computer, invented by the famous John von Neumann, is Merge Sort.

The idea is as follows:

1. Divide an array in half.

2. Sort each half.

3. Repeat this recursively.

4. Merge the halves.

Imagine an array where the first half is already in sorted order. And the same for the second half. Then imagine how you would merge these two halves to create a single sorted array. That’s what merge sort does.

Copy the two halves to a second array. Then we will create three indices. One of these will move along the left half of the second array (m). One of these will move along the right half of the second array (n), and one of these will keep the position of the result in the original array (i).

Step one is to compare the first item in the left half of the secondary array (at index m) to the first item in the right half of the secondary array (at index n) to see which is lower. Whichever one is lower is moved to the first position in the result array (at index i). Then the index of the result array (i) is incremented and the index of the moved item is incremented (either m or n).

And the process is repeated.

Intuitively, this is how you would merge two halves of an array where the two halves were sorted to begin with.

AND this is the first sort we’ve covered that works in O(n lg n) time.

func mergeSort(a: inout [Double]) {

    mergeSort(a: &a, lo: 0, hi: a.count-1)

}

func mergeSort(a: inout [Double], lo: Int, hi: Int) {

    if lo >= hi { return }

    let mid = (lo + hi) / 2

    mergeSort(a: &a, lo: lo, hi: mid)

    mergeSort(a: &a, lo: mid+1, hi: hi)

    merge(a: &a, lo: lo, mid: mid, hi: hi)

}

func merge(a: inout [Double], lo: Int, mid: Int, hi: Int) {

    let leftSubarray = Array(a[lo…mid])

    let rightSubarray = Array(a[mid+1…hi])

    var k = lo

    var i = 0

    var j = 0

    while i < leftSubarray.count && j < rightSubarray.count {

        if leftSubarray[i] < rightSubarray[j] {

            a[k] = leftSubarray[i]

            i += 1

        }

        else {

            a[k] = rightSubarray[j]

            j += 1

        }

        k += 1

    }

    while i < leftSubarray.count {

        a[k] = leftSubarray[i]

        k += 1

        i += 1

    }

    while j < rightSubarray.count {

        a[k] = rightSubarray[j]

        k += 1

        j += 1

    }

}