Insertion sort grows a sorted prefix of an array one entry at a time. In the adjacent-swap version, start with position , compare its current sort key with the preceding sort key, and swap the complete sorting records only when the right sort key is strictly smaller. Continue leftward until no swap is needed or the entry reaches position zero; then process original position . A tie stops the pass. This is the strict comparison and exchange rule in the authored implementation.[ref]
Take , where the subscript labels a complete sorting record and comparisons inspect only its sort key. Starting from index zero, the complete key-comparison trace is:
The loop invariant is that, before pass , positions satisfy sortedness and contain precisely the entries originally in that prefix. Moving the next entry left through strictly larger sort keys extends that prefix, and every swap retains sorting permutation preservation. Equal-key entries never cross, giving stable sorting. Each leftward step decreases the position, and each completed pass increases the prefix length, so the algorithm terminates.
With constant-cost key comparisons and swaps, reverse-ordered distinct sort keys cause comparisons and swaps. Thus worst-case time complexity is in Big O notation. An already sorted array needs only key comparisons for and no swaps. The adjacent-swap version uses constant auxiliary space complexity. Small or nearly sorted arrays can therefore make insertion sort useful despite its quadratic worst case.
Articles by others on the same topic
Insertion sort is a simple and intuitive sorting algorithm that builds a sorted array (or list) one element at a time by repeatedly picking the next element from the unsorted section and placing it in the correct position within the sorted section. It is often used for small datasets or partially sorted data due to its efficient performance in such cases. ### How Insertion Sort Works: 1. **Start with the first element**: Consider the first element as a sorted section.