Insertion Sort

This is the continuation of the last article on selection sort. Please check it if you didn’t read it yet.

The last of the slow algorithms we will talk about is insertion sort. This is the best performing algorithm for small arrays.

The idea is also very simple and like selection sort the array is also conceptually split into two parts, the sorted and unsorted parts.

In selection sort we first find the minimum element of the unsorted part and put it at the end of the sorted part but on insertion sort we just select each element and put it in the correct place, kind of like you would sort a deck of cards in your hand.

Let’s look at an example: [3, 5, 1, 2, 4]
We have the sorted empty array [] and the unsorted [3, 5, 1, 2, 4].
We select 3 and put it in the empty part: [3] + [5, 1, 2, 4]
Then we select 5 and go from right to left checking where is the place where we should insert it. 5 is bigger then 3 so we insert it there and get [3, 5] + [1, 2, 4].
Then we pick 1 and check where to put it:
It’s smaller than 5, we move left, it’s lower than 3, we move left and put it there and we get: [1, 3, 5] + [2, 4].

You get the idea. If you want a better idea, here is an animation that I took from Wikipedia.

The algorithm in Kotlin

fun <T : Comparable<T>> DynamicArray<out T>.insertionSort() {
    var sortedUntilIndex = 1
    while (sortedUntilIndex < size()) {
        var i = sortedUntilIndex
        while (i > 0 && this[i] < this[i - 1]) {
            swap(this, i, i - 1)
            i--
        }
        sortedUntilIndex++
    }
}

This algorithm took 22 minutes to sort the array on my machine.

Definitely the fastest of them until now but obviously still too slow.

For the next article we will learn about quick sort. An algorithm that is much faster than all three we learned before and will be the last one we will use because it’s enough for our purposes. You will see the dramatic difference in performance and it will become obvious why it makes sense for computer scientists to research this topic.

Thanks for reading and stay tuned for the next article.