Another algorithm that one might use in addition to selection sort when playing a card game is called Insertion Sort. While selection sort finds the smallest and continuously finds the next smallest, insertion sort might be a subtle algorithm that you use when sorting cards in your hand as they are dealt to you; Given one card, you place it in your hand to the left, and when another is dealt, you might "swap" the cards around to be in the correct order.

Assumptions

  • Knowledge of Big-O notation
  • Familiarity with The Master Theorem

What is Insertion Sort?

Insertion Sort is an in place, stable sorting algorithm that scans an array multiple times, swapping out of order elements until all elements in the list are in order.

This algorithm works well for small data sets, and nearly sorted arrays.

> Insertion Sort is also online; it can be sorted as new elements are being added to an array.

/* pseudo-code */
int [] array = { 5, 7, 3, 1, 9, 6, 8 };

function InsertionSort(int[] arr) {
    // Loop over the array.
    for ( int i = 0; i < arr.length; i++ ) {
        // Store the value of arr[i].
        int tmp = arr[i];
        int j = i - 1;
        // While the previous element is larger..
        while ( j >= 0 && arr[j] > tmp ) {
            // ..  Move the elements up a space (1).
            arr[j + 1] = arr[j];
            // decrement j.
            j = j - 1;
        }
        // Set the i-th value to be wherever j stops. 
        arr[j + 1] = tmp;
    }
}

Analysis:

  1. Some approaches to this might use a function called swap, i.e., swap( arr[j], arr[j-1] );. This works, however the implementation shown shifts the numbers up until arr[j] <= tmp. This gives a savings in some systems where memory writes are expensive as it is only writing each place once where swap writes twice.

Analyzing Insertion Sort

When Insertion Sort is scanning the array, it will only "swap" an element if it contains an inversion, i.e., an array of [2, 1, 3, 4] contains an inversion of 2 and 1. If the array does not contain any inversions, then the best possible case for this sorting algorithm is O(n) time to execute. For this reason, Insertion sort is ideal to use when a given array is nearly sorted.

The worst case scenario, though, occurs when an array is in reverse order. When this is the case, each item must be swapped all the way through the array for each element, meaning that it will take at worst O(n<sup>2</sup>) time to sort the array.

Best Average Memory
O(n) O(n<sup>2</sup>) O(1)

Sorting Cards

Going back to the deck of cards example, let's sort a hand of seven cards using insertion sort. Let's start out with our deck of cards like so:

<div style="width:100%; margin:auto;text-align:center;display:inline-block;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_InsertionSort_01.png" alt="unsorted cards" style="max-width:95%;">

</div>

Starting from the left card, there are no previous cards to compare, so we move onto the second from the left. Here, we see that 2 < 5, so we swap the two cards.

<div style="width:100%; margin:auto;text-align:center;display:inline-block;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_InsertionSort_02.png" alt="cards with first element sorted" style="max-width:95%;">

</div>

Now at the third card, we see that it is in order, so we continue onto the next card. The same applies for the next two cards, so we continue until we reach the 6th card. We see that 4 < 10, so we go backwards in the array, swapping cards, until we find a card n &lt;= 4.

<div style="width:100%; margin:auto;text-align:center;display:inline-block;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_InsertionSort_03.png" alt="cards with two elements sorted" style="max-width:95%;">

</div>

Now there is the final card, 6. We notice 6 < 10, so just like we did with 4, we go backwards in the array, swapping cards until we find a card n &lt;= 6.

<div style="width:100%; margin:auto;text-align:center;display:inline-block;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_InsertionSort_04.png" alt="cards with all elements sorted." style="max-width:95%;">

</div>

Finally having reached the end of the array, we know the cards are now in sorted order!

When to use Insertion Sort

Insertion sort has a best case of O(n) when the array is already sorted, and O(n<sup>2</sup>) when the array is sorted in reverse order. For this, it makes sense that it would work best when working on an array that you know is nearly sorted apart from a few entries.

Further Resources