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.
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.
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
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).
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.
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
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.