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

Implementations

LSL
ARexx