Insertion sort and selection sort

In short: Insertion sort and selection sort are simple sorting methods with running time O(n²). For small amounts of data they are practical.

In more detail: Selection sort finds the smallest remaining element in each pass and puts it at the front. Insertion sort takes each element in turn and slides it to the right place in the already sorted part, like sorting playing cards in your hand.

In Depth

• Insertion sort: stable, in the best case (almost sorted) O(n), fast on small lists. That is why many libraries use it for short pieces.
• Selection sort: few swaps (at most n−1), but always O(n²) comparisons.
• Stable: equal elements keep their order.
• Comparison: Bubblesort is similarly simple but usually slower. For large lists use Mergesort or Quicksort.
• Insertion sort example: [5, 2, 4, 1] → [2, 5, 4, 1] → [2, 4, 5, 1] → [1, 2, 4, 5].

See also: Sorting, Advanced sorting