Animated Sorting Algorithm Demo: Insertion Sort

Algorithm

# move min to front, as sentinel
k = 1
for i = 2:n, if a[i] < a[k], k = i
swap a[1,k]
invariant: a[1] <= a[2..n]

# insertion sort with sentinel
for i = 2:n,
    for (k = i; a[k] < a[k-1]; k--) swap a[k,k-1]
    invariant: a[1..i] is sorted
end
        

Properties

• Stable
• In place: O(1) extra space
• Worst case O(n²) comparisons and swaps
• Adaptive: O(n) when nearly sorted
• Very low overhead

Discussion

Although it is one of the elementary sorting algorithms with O(n²) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (due to its low overhead). For these reasons, and because it is also stable, insertion sort is often used as the base case (when the problem size is small) for more complex algorithms that have higher overhead such as quicksort.

Directions

• Click on to restart the animations.
• Click on a size number to change the size of the examples.
• Click on a cell to restart an individual animation.
• Click on a cell title to explore that input order.

Key

• Black values are sorted.
• Gray values are unsorted.
• A red triangle marks the algorithm position.

References

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.