insertion sort

A simple sort that takes items one at a time and shifts each left into its correct place among those already sorted.

In more detail

Insertion sort is O(n^2) on random data but close to O(n) on nearly sorted data, because each item moves only a little. It is stable, in place and fast on small inputs, which is why real sort routines use it for short runs. The course counts its comparisons against merge sort and quicksort.

Related terms

Taught in

References