3 ms·
insertion sort only ever makes one outer pass; it does almost exactly half as many comparisons as bubble sort (n rather than 2n-2) in that case, and the same nu
by kragen 3y ago
insertion sort only ever makes one outer pass; it does almost exactly half as many comparisons as bubble sort (n rather than 2n-2) in that case, and the same number of swaps (1)
the wikipedia article has a cleverer early-exit version of bubble sort that keeps track of the last pair it had to swap; it will do 1.5n-1 comparisons in that case on average (because the swapped pair is on average in the middle of the array)
above i linked to working code on godbolt (modulo the extra unnecessary swaps on duplicate keys that you were kind enough to point out earlier); edit a comparison counter and a swap counter into it and you'll see