A bubble sort over a nearly-ordered status list ships without a swapped flag — what does that cost?

## The code under review ``` n = length(a) for i in 0..n-2 for j in 0..n-2-i if a[j] > a[j+1] swap(a[j], a[j+1]) ``` This is correct — it sorts. The defect is that the outer loop is a fixed count: it runs n-1 passes whether or not the data still needs them. Feed it a list that is already in order and it performs n(n-1)/2 comparisons and zero swaps, doing quadratic work to discover that there was nothing to do. ## The fix and why it is sound ``` n = length(a) for i in 0..n-2 swapped = false for j in 0..n-2-i if a[j] > a[j+1] swap(a[j], a[j+1]) swapped = true if swapped == false break ``` The correctness argument is short and worth being able to state out loud: if a full pass performs no swap, then for every adjacent pair `a[j] <= a[j+1]`. Under a total order, pairwise adjacent ordering across the whole array implies global ordering by transitivity. So a clean pass is a *proof of sortedness*, and stopping is safe. Cost after the fix: - **Best case** (already ordered): one pass, n-1 comparisons, 0 swaps — O(n). - **Worst case** (reversed): unchanged, n(n-1)/2 comparisons and swaps — O(n^2). The flag never fires early on adversarial input. - **Swaps**, with or without the flag: exactly the number of inversions in the input. ## The part candidates get wrong: what "nearly ordered" buys It is tempting to say the flag makes the algorithm linear on nearly-ordered data. That is too strong, and an interviewer will push on it. The number of passes is governed by how far elements have to move **toward the front**, because each pass moves a given element at most one position left. Concretely: - A list that is ordered except that a few values sit slightly *ahead* of where they belong — those large values are carried right quickly, so the flag fires after a couple of passes. Genuine win. - A list that is ordered except that the single smallest value sits at the very end — it crawls one slot left per pass, so about n passes still run. The flag saves almost nothing. The honest statement is: with early exit, the pass count is roughly one more than the maximum leftward distance any element must travel. That asymmetry is a property of adjacent-exchange scanning, and it is exactly the sort of directional detail that separates a memorised answer from an understood one. ## The other bound in the loop Note the inner bound `n-2-i` rather than `n-2`. It skips the tail that is already final, roughly halving the total comparisons. This is a constant-factor improvement only — it does not change the complexity class, and it is independent of the flag. A review comment should distinguish the two: the shrinking bound is an optimisation, the flag is a change of best-case complexity. ## How to write the review comment On a status list that is nearly ordered most of the time — the realistic case, since the list is re-sorted after small updates — the missing flag means the common path pays the worst-case comparison count on every call. The suggested change is three lines, does not alter the result, and turns the common path linear. If someone objects that "bubble sort is O(n^2) anyway", the answer is that O(n^2) is the *worst-case upper bound*; best case with the flag is O(n), and the code as written never reaches it. Worth pairing with a second, larger comment: at any size where the quadratic term matters, the right fix is not tuning this loop but choosing a different algorithm entirely. The flag is what you ask for when the list is small and the algorithm is staying. ## Common wrong answers - "Bubble sort is O(n^2), period." It is O(n^2) worst case; with the early exit the best case is O(n). - "The flag improves the worst case." It does not; reversed input still costs quadratic time. - "With the flag, any nearly-ordered input is linear." Only if no element has to travel far leftward. - "It is just a constant factor." On ordered input it is the difference between n and n^2 comparisons.