Insertion Sort

Algorithm

For every element in the list, pick the element and place it at its corresponding position, either before or after the previous element.

Performance

Worst case: $O(n^{2})$ comparisons and swaps
Best case: $O(n)$ comparisons, $O(1)$ swaps
Average case: $O(n^{2})$ comparisons and swaps
Space complexity: $O(n)$ total or $O(1)$ auxiliary

Properties

An invariant is that all the items on the left-hand side that have been inserted will remain in-order after every iteration.

Implementations

LSL
ARexx