= Insertion sort
{wiki}
<Insertion sort> grows a sorted prefix of an <array> one entry at a time. In the adjacent-swap version, start with position $i=1$, 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 $i+1$. A tie stops the pass. This is the strict comparison and exchange rule in the authored implementation.<Insertion.java by Robert Sedgewick and others>{ref}
Take $A=(2_A,1_B,2_C,1_D)$, 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:
|| Comparison
|| Right <sort key> smaller than left?
|| Action
|| <Array> after the action
| 1, insert position $1$
| $1_B<2_A$: yes
| Swap positions $0,1$.
| $(1_B,2_A,2_C,1_D)$
| 2, insert position $2$
| $2_C<2_A$: no
| Stop this pass on a tie.
| $(1_B,2_A,2_C,1_D)$
| 3, insert position $3$
| $1_D<2_C$: yes
| Swap positions $2,3$.
| $(1_B,2_A,1_D,2_C)$
| 4, continue leftward
| $1_D<2_A$: yes
| Swap positions $1,2$.
| $(1_B,1_D,2_A,2_C)$
| 5, continue leftward
| $1_D<1_B$: no
| Stop this pass on a tie.
| $(1_B,1_D,2_A,2_C)$
\Image[/sorting-stable-insertion-compare-swap-trace.png]
{title=<Insertion sort>: five <sort key> comparisons and three complete-entry swaps}
{id=sorting-stable-insertion-compare-swap-trace}
{description=Each row after the <input> shows the state after one comparison. Orange cells mark an adjacent swap; green cells mark a stopping tie. Identity letters are not compared. Both equal-key groups retain their <input> order, demonstrating <stable sorting>.}
The <loop invariant> is that, before pass $i$, positions $0,\ldots,i-1$ 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 $1+2+\cdots+(n-1)=n(n-1)/2$ comparisons and swaps. Thus worst-case <time complexity> is $O(n^2)$ in <Big O notation>. An already sorted <array> needs only $n-1$ key comparisons for $n\geq1$ 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.
Back to article page
