Insertion Sort

Notes

Insertion sort is one way to sort an array of numbers. Data is divided into sorted and unsorted portions. One by one, the unsorted values are inserted into their appropriate positions in the sorted subarray.

Let's use insertion sort to sort the elements of this array in ascending order.

Insertion sort relies on breaking up the array into sorted and unsorted portions.

Before we start sorting, all values are considered unsorted.

On our first pass, we'll take the first unsorted value (3) and insert it into the sorted subarray. 3 is now the start and end of our sorted subarray.

Since 5 > 3, we'll insert it to the right of 3 in our sorted subarray.

Next we'll work on inserting 2 to our sorted subarray.

We'll compare 2 to the values in the sorted subarray from right to left to find it's correct sorted position. We see that 2 < 5 and 2 < 3. We've reached the beginning of the sorted subarray, so we know that 2 must be inserted to the left of 3. This forces us to shift 3 and 5 rightwards to make room for 2.

6 is an easy one. 6 > 5, so it can be inserted to the right of 5.

4 < 6 and 4 < 5, but 4 > 3. Therefore, we know that 4 must be inserted to the right of 3.

Again, we are forced to shift 5 and 6 rightwards to make room for 4.

In summary, here's the insertion sort algorithm:

Take each unsorted element, n, and compare it to values in the sorted subarray from right to left until you determine the appropriate sorted position for n.

Shift sorted elements rightward as necessary to make space for n, and insert the previously unsorted n into its appropriate position in the sorted subarray.

And here's some pseudocode to implement insertion sort in C. Try it yourself!

In the worst case, we'd make one comparison for the second element, two comparisons for the third element, and so on. We'd end up with O(n2).

In the best case, we'd run insertion sort on an already sorted list. The sorted portion would simply be built up from left to right without a large number of comparisons and no complicated shifting of elements so best case runtime would be Ω(n).

What would the best case runtime of insertion sort be if we iterated through the sorted portion of the list from left to right (rather than right to left) when determining where to insert the next unsorted element?

n2

Although insertion sort and selection sort are very similar, you can see that insertion sort's best case runtime, n, is significantly more efficient than selection sort's best case runtime, n2.

Here's a comparison of the runtimes of insertion sort to the runtimes of other sorting algorithms covered in CS50.

Slides ( / )

study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide

(Insertion) Sort the Array

Prerequisites:

Use insertion sort to sort the array.

jharvard@run.cs50.net (~): ./a.out
4 15 16 50 8 23 42 108
4 8 15 16 23 42 50 108

Try out some pseudocode here!
#include <stdio.h>

#define SIZE 8

void sort(int array[], int size)
{
    // TODO: sort array using insertion sort
}

int main(void)
{
    int numbers[SIZE] = { 4, 15, 16, 50, 8, 23, 42, 108 };
    for (int i = 0; i < SIZE; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
    sort(numbers, SIZE);
    for (int i = 0; i < SIZE; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
}

Videos

study50 video thumbnail

Wednesday, Week 3

An introduction to sorting algorithms
study50 video thumbnail

Tommy's Insertion Sort Short

Tommy gives a general overview