Insertion Sort

[Ganon11]

So far, the Articles sections are filled with slow sorting algorithms. Bubble Sort and Selection Sort, while very easy to comprehend, are relatively slow algorithms at Θ(n^2) running time. Here, I will try to explain an algorithm to sort an array of numbers that is fast for small sets of data, though it is still an O(n^2) algorithm; the Insertion Sort.

Suppose we have an array of n-1 elements that is already sorted in increasing order. We then come to the nth element (let us call it x) to be ‘inserted’ into this sorted array. It follows that there is some portion of the array in which the elements are less than x, and another portion in which the elements are greater than x. Further, because we know that the existing array is sorted, we know that the array generally looks like this:

[elements < x][elements>x]

We begin the algorithm by creating a hole at the end of the array:

[elements<x][elements>x][empty hole]

Now, we want to have our array completely sorted for all n elements at the end, so the alert reader may realize that the array must look like this when we are done at this step:

[elements<x][x][elements>x]

It follows that all of the elements greater than x must shift down the array one slot. We can, in fact, do this very simply by moving any element a[j] to a[j+1] as long as a[j] is greater than x. We start this moving at the element just before the hole and continue until the element we check is less than x. Now every element has been shifted one slot and overwritten every previously copied value except for the last to be shifted, of which there remains 2 copies adjacent to each other. We know that this element is greater than x (or else we would not have shifted it) and so we place x in the position that element originally held.

A powerful note to this algorithm is that it can be implemented to use no extra space. If we consider only the first I elements of any array as our sorted array, then creating a hole is as simple as increasing our array’s size, making a copy of the last term (which must be inserted into its sorted position), and following our steps above. The algorithm in pseudocode is presented below:

void insertion_sort(int[] array) {
    for (Loop i from 1 to array.size-1)
        int x = array[i]
        int j = array[i-1]
        while (j >= 0 && array[j] > x)
            array[j+1] = array[j]
            j = j - 1
        array[j+1] = x
}