Insertion sort
Builds a sorted part on the left, one value at a time. Each new value is taken out and moved left until it reaches a smaller value.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- yes
- yes
Best case: how the time grows with the list size n when the input is the easiest for this algorithm.
Average: the usual growth of time with n. n² means twice as many values take about four times as long; n log n grows much more slowly.
Worst case: the growth on the hardest input. Useful when speed must never drop.
Space: how much extra memory is needed besides the list. 1 means a few variables, n means a copy of the list.
Stable: two equal values keep their original order. Matters when sorting by one field of a record.
In place: sorts inside the list itself, with no second list.
- comparing
- moving
- in hand
- sorted part
- in final place
Try this: Pick a nearly sorted list. Almost nothing shifts, so it finishes in very few steps.
How it works
The left part is always sorted. Take the next value out, move every bigger value in the sorted part one place to the right, then put the value into the gap. This is how many people sort playing cards in their hand.
When it is a good choice
A good choice for short lists and for lists that are almost sorted, where it is very fast. Real sorting libraries use it for the small pieces of a list inside faster methods.