What it costs
- Best case
- O(n²)There is no best case. The inner scan always runs to the end of the array, because nothing tells it the remainder is already sorted.
- Average
- O(n²)Exactly n(n−1)/2 comparisons — try every preset and watch the number land identically each time.
- Worst case
- O(n²)Also exactly n(n−1)/2. Reversed, random and already-sorted input cost the same.
- Swaps
- ≤ n−1Its one real virtue: at most one swap per position. When a write is expensive — flash memory, large records — that can matter more than the comparison count.
- Extra memory
- O(1)It tracks an index, not a copy.
- Stable
- NoThe long-range swap can throw an equal value past its twin. Sorting
[4a, 4b, 1]swaps the 1 with the first 4, and the two 4s come out reversed.
Against insertion sort: same O(n²) worst case, but insertion sort collapses to O(n) on sorted input while this one cannot. Run both on Already sorted — the comparison counts tell the whole story.