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.
Top comments (2)
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)
I state that in the
Time: Copies
section.