Insertion

Today we’ll get into a practical sort that is actually used in real system sorts in specific cases: Insertion sort.

But let’s first consider the Selection Sort again. The code is repeated below.

It traverses the array using two loops. The outer loop moves the index i from left to right  and exchanges the value at index i with the minimum value in the unsorted array to the right of i. The inner loop traverses the unsorted array to the right of i to find that minimum value. The inner loop must traverse to the end of the unsorted portion for each value of i.

public func selectionSort(a: [Double]) -> [Double] {

    var b = a

    for i in 0..<b.count {

        var min = i

        for j in (i+1)..<b.count {

            if b[j] < b[min] {

                min = j

            }

        }

        b = exchange(a: b, i: i, j: min)

    }

    return b

}

public func exchange(a: [Double], i: Int, j: Int) -> [Double] {

    var b = a

    let temp = b[i]

    b[i] = b[j]

    b[j] = temp

    return b

}

Consider Selection Sort further: There are two ‘invariants’ that we must accommodate with this method. First, we have i in the outer loop. All entries in the array to the left of i are sorted and in ascending order. This is an invariant. No entry to the right of i is smaller than the entry at i. This is an invariant.  The code we’ve written makes these invariants work. When we move i, then there now might be an element to the right of i that is smaller. So the code implements an exchange and fulfills the requirements of the invariant.

This method uses about n²/2  compares to achieve the result. Clearly this is undesireable, because we never want to use an algorithm that uses n² compares or anything proportional to n² such as kn². It’s always too slow when n becomes large. And notice further that the inner loop ALWAYS traverses all the values that are unsorted for each value of i — even if the values are already in sorted order.

Insertion Sort is another simple sorting method, but it has very different qualities than Selection Sort.

Consider an outer loop with an index i that traverses an array from left to right. But this time, we are only going to concern ourselves with elements of the array at i or to the left of i. And we are going to keep these elements in sort order.

Consider the following array of doubles:

var a: [Double] = [12, 23, 3, 54, 4, 7, 4, 2, 9, 8, 6, 10]

So starting out, when i is index of 0, the value at i is 12. And since it’s the first value, it is in sorted order and we do nothing.

When i is 1, the value of i is 23. And comparing a[1] to a[0], we see the array to the left of i is still in sorted order, so we do nothing.

When i is 2, the value of i is 3. Now we move that value to the left until it is in the correct position:

a = [3, 12, 23, 54, 4, 7, 4, 2, 9, 8, 6, 10]

Next when i is 3, the value of i is 54, and the array to the left of i is still in sorted order so we do nothing.

When i is 4, the value of i is 4, so we move that element to the left until all elements to the left of i are in sorted order again:

a = [3, 4, 12, 23, 54, 7, 4, 2, 9, 8, 6, 10]

Here the invariant is that the elements to the left of i are always in order.

The code for this in Swift is:

public func insertionSort(a: [Double]) -> [Double] {

    var b = a

    for i in 0..<b.count {

        for j in (0…i).reversed() {

            if j-1 >= 0,b[j] < b[j-1]  {

                b = exchange(a: b, i: j, j: j-1)

            } else {

                break

            }

        }

    }

    return b

}

You can see that it is very similar to Selection Sort, each having two loops and a comparison. But in this case, the inner loop is doing less work. And while selection sort has about n^2/2  compares, insertion sort has about about n^2/4  compares. So it will go about twice as fast.

However, if the array is already sorted in reverse order, then the inner loop has to bring every element to the beginning of the array. In that case the number of compares approaches about n2/2  compares. Thus, Insertion Sort usually works best when the array is in random order or partially sorted.

Consider the case when the array is partially sorted, as in a large array that is sorted with just a few entries flipped. In real life, a partially sorted  array happens often. Imagine that you have a large array of patients in your health app or customers at your online store, and they are to be sorted by last name. And a patient arrives and sees that their last name is misspelled in your database. In this case you correct the misspelling, but now the array of all patients is out of order at one position. This is called an inversion.

Furthermore, imagine that over time this happens repeatedly, and the order of your array degrades but only in a few places and only with inversions. So let’s say, you have an array with 100 elements but 6 inversions. The presentation of your patients in the dropdown requires that the patients all be in order, so you have to sort them.

Insertion sort is valueable here because it will sort an array with inversions in linear time — proportional to the number of elements in the array. And this is very fast. This is one of the reasons that Swift ‘sort’ and other system sorting methods will use insertion sort in their hybrid algorithms if the number of elements in the array is less than about 20: It sorts in place. A time space of n^2/4  compares is not great — but for 20 items it doesn’t matter, so Insertion sort can be valuable in some system sorting methods.