DEV Community

loading...
Cover image for Insertion Sort Quick Reference

Insertion Sort Quick Reference

edA‑qa mort‑ora‑y
I'm a creative programmer and puzzles designer. I cook monsters.
Originally published at interview.codes ・2 min read

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
Enter fullscreen mode Exit fullscreen mode

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.

Discussion (2)

Collapse
theodesp profile image
Theofanis Despoudis • Edited

O(n · log n) is not entirely correct as if you are counting comparisons then yes it's O(n · log n) but if you want to insert an element in the middle of the array you have to shift all the items right by one. Thus it can cost as much as n so the total cost can be:
O(n2)

Collapse
mortoray profile image
edA‑qa mort‑ora‑y Author

I state that in the Time: Copies section.