Insertion sort is a commonly taught algorithm for sorting a list of items. Though not commonly used, as it's not efficient, it may come up during interviews. It also uses concepts that might be beneficial when writing other algorithms. This is a quick reference for insertion sort.

Algorithm Design

Insertion sort takes an unsorted list and produces a sorted version of it.

It is a stable sorting algorithm.

Insertion-Sort( input )
    output = empty list
    for each item in the input
        find location item in the output using upper bound (binary search)
        insert item at location in the output

Refer to sample code in Python.

Algorithm Complexity

Time: Comparisons

The number of comparisons it the number of times two items are compared with each other. This is typically done using only the less than < comparison.

For each item in the list n, the algorithm searches for the correct location using binary search O(log n). This puts an upper bound on the number of comparisons at O(n · log n).

Time: Copies

The number of copies is the number of times an item is copied to a new location, either from the input or within the output.

All items must be copied from the input to output, making a minimum of Ω(n) operations. If the input is in sorted order, this will be the number of copy operations.

In the worst-case scenario the list is sorted in reverse order. In this scenario each insertion into the output will need to move all existing items in the list. For each n items, there could be up to n copy operations. This is O(n²) copy operations.

Space

The algorithm needs to allocate space in the output for each item in the output. It needs no additional space. This is a space complexity of θ(n).

Notes

Due to its costly time complexity for copy operations, insertion sort is not typically used to sort a list. It is however an efficient way to insert a limited number of items into an already sorted list.

Inserting one item with insertion sort is O(log n), whereas adding an item to a list and resorting is O(n · log n).

View my video class that covers the design, complexity, and code of the algorithm.