The interactive player is loading. If it does not appear, you can still read the explanation below.
How it works
This stable adjacent-swap variant of insertion sort selects the next value as a key and moves it left while its predecessor is larger. The sorted prefix grows after each insertion, but its values can still move during later insertions. Equal values never cross.
Already sorted values need n − 1 comparisons for n ≥ 1 and no swaps: O(n) best-case time. Reverse-sorted distinct values need n(n − 1) / 2 comparisons and adjacent swaps: O(n²) worst-case time. For uniformly random permutations of distinct values, average time is O(n²). Nearly sorted arrays usually need less work.
Empty arrays and single values require no comparisons. The algorithm uses O(1) extra space; the animation stores additional snapshots for playback. This visualization uses adjacent swaps rather than the alternative implementation that shifts values.