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
- comparison sort — A sorting algorithm that learns about the order only by asking "is a smaller than b?" about pairs of items.
- stable sort — A sort that keeps items with equal keys in the same relative order they had before sorting.
- in-place algorithm — An algorithm that rearranges its input within the input's own memory, using only a constant amount of extra space.
- quadratic time — Work that grows with the square of the input, written O(n^2): twice the items, four times the work.
Taught in
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers