Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
The number of swaps bubble sort performs equals the number of INVERSIONS in the array — pairs (i, j) with i < j but arr[i] > arr[j] — because each adjacent swap fixes exactly one inversion. Simulate bubble sort for O(n²), or count inversions with a modified merge sort for O(n log n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you connect bubble sort's swap count to the number of inversions, and whether you know inversions can be counted in O(n log n) via merge sort rather than the obvious O(n²) simulation.
Where candidates slip
Counting comparisons instead of swaps, or assuming bubble sort always does ~n² swaps (it does ~n² comparisons but swap count depends on disorder), or overflowing int on large reverse-sorted inputs.
How to stand out
State the invariant 'one adjacent swap removes exactly one inversion', conclude swaps = inversions, and offer the merge-sort O(n log n) count as the scalable alternative to simulation.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCount bubble-sort swapsHow big is n?SmallLargeExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Simulate Bubble Sort and Count (Baseline)
1Hint 1Explore hintHide hint
The problem literally gives you the algorithm. What's the most direct way to find the swap count?
2Hint 2Explore hintHide hint
Run the nested-loop bubble sort exactly as written and increment a counter on every swap.
3Hint 3Explore hintHide hint
Add an early-exit flag: if an entire inner pass performs no swap, the array is sorted and you can stop — this doesn't change the count but speeds up nearly-sorted inputs.
A · Core idea
Run bubble sort precisely as specified: repeatedly sweep the array, and whenever a[j] > a[j+1], swap them and increment a counter. After all passes the array is sorted and the counter holds the total swaps.
Why this is the faithful baseline. The prompt hands you the exact algorithm, so simulating it is unambiguously correct. It also demonstrates the key theorem rather than asserting it: every swap you count is an adjacent exchange that fixes one out-of-order neighbour pair.
Why each swap removes exactly one inversion. An inversion is a pair (p, q) with p < q and a[p] > a[q]. Swapping two adjacent elements a[j] and a[j+1] (because a[j] > a[j+1]) changes the order of only that one pair — every other pair keeps the same relative order, since their positions relative to each other are untouched. So one adjacent swap decreases the inversion count by exactly one. Bubble sort terminates when there are zero inversions (sorted), so the number of swaps it makes equals the number of inversions it started with — no more, no less.
Why the early-exit flag matters. Track whether the current pass made any swap. If a full pass is swap-free, the array is already sorted and the remaining passes would do nothing. This converts the best case (already sorted) from O(n²) to O(n) comparisons. It never changes the swap count — it just stops wasting comparisons.
Why it doesn't scale. The comparison work is quadratic regardless of the flag's help on adversarial inputs. At n = 10⁵, ~10¹⁰ comparisons is far too slow, which is why we reframe the count as inversions and use merge sort.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
a = [3, 2, 1]Array state
j=0
3 > 2 → swap (swaps=1)
3C · Code with teaching comments
Reference implementation previewpublic long countSwaps(int[] a) { long swaps = 0; int n = a.length; for (int i = 0; i < n; i++) { boolean swapped = false;Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Simulating bubble sort isn't just an answer — it's the proof. Watching each swap erase exactly one inverted neighbour pair is what licenses the leap to 'swaps = inversions', and from there to an O(n log n) count without simulating anything.
ComplexityO(n²) time, O(1) space — The outer loop runs up to n times and the inner up to n−1, so O(n²) comparisons. Swaps performed range from 0 to n(n−1)/2; we only use O(1) extra space.
E · Edge cases and pitfalls6a = [1, 2, 3] — First pass makes no swap → flag stays false → break after one pass, returns 0.Explore edge casesHide edge cases
Edge cases handled
a = [1, 2, 3]First pass makes no swap → flag stays false → break after one pass, returns 0.a = [5, 4, 3, 2, 1]Reverse sorted → n(n−1)/2 = 10 swaps, the maximum.a = [2, 2, 2]No strict greater-than ever holds → 0 swaps; duplicates are not inversions.
Pitfalls
- Counting comparisons instead of swaps — comparisons are always ~n².
- Using a 32-bit counter — overflows on large reverse-sorted arrays.
- Quadratic time times out for n near 10⁵.
Approach 2 of 2 · Optimal
Count Inversions via Merge Sort (Optimal)
1Hint 1Explore hintHide hint
You've argued each adjacent swap kills one inversion, so the swap count equals the inversion count. Can you count inversions without sorting one swap at a time?
2Hint 2Explore hintHide hint
Merge sort splits the array, sorts each half, and merges. During the merge of two sorted halves, when do you learn that an element is out of order with several others at once?
3Hint 3Explore hintHide hint
When you take an element from the RIGHT half before the left half is exhausted, that right element is smaller than every remaining left element — so add (number of remaining left elements) to the inversion count.
A · Core idea
Because bubble-sort swaps equal inversions, we can drop the simulation and just count inversions — and merge sort counts them almost for free while it sorts.
The merge-sort counting trick. Merge sort recursively sorts the left and right halves, then merges them into one sorted run. During the merge we have two pointers, one into the sorted left half and one into the sorted right half, and we repeatedly take the smaller front element. Here's the key: if the front of the right half is smaller than the front of the left half, then that right element is smaller than every element still remaining in the left half (the left half is sorted, so its front is its minimum). All of those remaining left elements originally sat before this right element but are larger than it — each is an inversion. So we add (mid − i + 1), the count of remaining left elements, to the running total in one shot.
Why this captures every inversion exactly once. Any inverted pair (p, q) with p < q and a[p] > a[q] ends up with a[p] in some left half and a[q] in the corresponding right half at exactly one level of the recursion — the level where the split separates them. At that merge, a[q] is taken before a[p], and a[p] is among the 'remaining left elements' counted. Pairs within the same half are counted deeper in the recursion. So each inversion is tallied once and only once.
Why it's O(n log n). The recursion has log n levels; each level merges disjoint runs covering all n elements, so each level is O(n). The inversion bookkeeping is a single addition per 'take from right' step, which doesn't change the asymptotics. This is the standard merge-sort cost, and it's the best achievable in the comparison model for counting inversions.
Why the 64-bit accumulator is non-negotiable. A reverse-sorted array of n = 10⁵ has n(n−1)/2 ≈ 5×10⁹ inversions, well past the 32-bit signed limit of ~2.1×10⁹. Accumulate in long (Java) — Python's integers are unbounded, so only Java is at risk.
Why we still get the array sorted as a side effect. The merge sort really does sort a; the inversion count is gathered along the way. If the caller also wants the sorted array (some variants ask for first/last element after sorting), it's already produced.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
a = [2, 1, 3, 1, 2]Interactive diagram
Counting inversions during a merge
splitWhen a right-half element is taken early, every remaining left element forms an inversion with it.
4C · Code with teaching comments
D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The reframing — 'swaps = inversions' — is what unlocks the speedup. Once a quantity is recognised as an inversion count, merge sort (or a BIT/Fenwick tree) computes it in O(n log n). This same divide-and-conquer counting move solves Count of Smaller Numbers After Self and Reverse Pairs.
ComplexityO(n log n) time, O(n) space — Merge sort is O(n log n): log n levels of merging, each level touching all n elements once. The inversion counting adds only O(1) work per merge step. Temporary buffers cost O(n) space.
E · Edge cases and pitfalls6a = [1, 2, 3, 4] — Every merge always takes from the left first → 0 inversions → 0 swaps.Explore edge casesHide edge cases
Edge cases handled
a = [1, 2, 3, 4]Every merge always takes from the left first → 0 inversions → 0 swaps.a = [4, 3, 2, 1]Every right element passes all remaining left elements → 6 inversions for n = 4.a with 10⁵ reverse-sorted values~5×10⁹ inversions — correct only with a 64-bit accumulator.
Pitfalls
- Using a[i] < a[j] instead of <= — counts equal elements as inversions, over-counting swaps.
- Adding 1 per inversion instead of (mid − i + 1) — degrades to O(n²) and misses the batch insight.
- Forgetting to copy the merged run back — parent merges then operate on unsorted halves and miscount.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic long countSwaps(int[] a) { int[] buffer = new int[a.length]; return mergeCount(a, buffer, 0, a.length - 1); } Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Counting comparisons instead of swaps
Incrementing on every comparison, not every actual exchange, reports ~n² regardless of disorder — the wrong quantity.
Explore the code comparisonHide the code comparison
Counting comparisons instead of swaps
Incrementing on every comparison, not every actual exchange, reports ~n² regardless of disorder — the wrong quantity.
Don't write this
for (int j = 0; j < n - 1; j++) {
swaps++;
if (a[j] > a[j + 1]) { /* swap */ }
}Write this instead
for (int j = 0; j < n - 1; j++) {
if (a[j] > a[j + 1]) {
/* swap */
swaps++;
}
}232-bit overflow on the swap count
A reverse-sorted array of 10⁵ elements has ~5×10⁹ inversions, which wraps a 32-bit int negative.
Explore the code comparisonHide the code comparison
32-bit overflow on the swap count
A reverse-sorted array of 10⁵ elements has ~5×10⁹ inversions, which wraps a 32-bit int negative.
Don't write this
int swaps = 0;
// ... count up to n(n-1)/2 ...
return swaps;Write this instead
long swaps = 0;
// ... count up to n(n-1)/2 ...
return swaps;3Strict-less merge that miscounts equal elements
Bubble sort swaps only on strictly greater, so equal elements are not inversions. Using a[i] < a[j] makes the merge take right elements on ties and over-count.
Explore the code comparisonHide the code comparison
Strict-less merge that miscounts equal elements
Bubble sort swaps only on strictly greater, so equal elements are not inversions. Using a[i] < a[j] makes the merge take right elements on ties and over-count.
Don't write this
if a[i] < a[j]:
merged.append(a[i]); i += 1
else:
merged.append(a[j]); j += 1; count += (mid - i + 1)Write this instead
if a[i] <= a[j]:
merged.append(a[i]); i += 1
else:
merged.append(a[j]); j += 1; count += (mid - i + 1)Revise
Carry the pattern into the interview
Pattern to remember
Bubble sort swap count = inversion count (merge-sort to count in O(n log n))
Code pattern to memorize
swaps = number of pairs (i, j), i < j, arr[i] > arr[j]
O(n²): simulate bubble sort, ++swaps on every adjacent exchange
O(n log n): merge sort; while merging, when right element is taken before remaining left elements, add (mid - i + 1) to the countRules to remember
- 1Each adjacent swap removes exactly one inversion — so total swaps = total inversions, independent of how bubble sort schedules them.
- 2Bubble sort is O(n²) comparisons but the number of swaps can be anywhere from 0 (sorted) to n(n−1)/2 (reverse sorted).
- 3Add an early-exit flag: if a full pass makes no swap, the array is already sorted — turns best case into O(n).
- 4To count inversions fast, piggyback on merge sort: every time you pull an element from the right half before the left half is exhausted, it jumped over all remaining left elements.
- 5Use a 64-bit accumulator — n(n−1)/2 for n = 10⁵ is ~5×10⁹, which overflows 32-bit int.
Use this pattern when
- You need the count of adjacent swaps to sort, or 'how far from sorted is this array?'
- A problem reduces to counting inversions (pairs out of order)
- Teaching/derivation contexts where the bubble-sort ↔ inversions link is the point
- Small n where O(n²) simulation is acceptable, or large n needing the merge-sort count
Choose another pattern when
- You only need the array sorted, not the swap count → use a real O(n log n) sort and move on
- Swaps can be non-adjacent (selection-sort style) → swap count ≠ inversions
- n is large and you simulate bubble sort → O(n²) will time out; count via merge sort
- You forget the 64-bit accumulator → overflow on near-reverse-sorted big inputs
Interview takeaway
The headline result is bubble-sort swaps = inversions. Once you see that each adjacent swap fixes exactly one out-of-order pair, you can count swaps in O(n log n) with merge sort instead of simulating the quadratic process — a classic 'reframe the count' interview move.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternBubble-sort swaps = inversions, counted in O(n log n) by merge sort. Recognise the reframe whenever a problem counts adjacent exchanges or 'how unsorted' an array is. The merge-step counting trick generalises to Count of Smaller Numbers After Self and Reverse Pairs.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Count of Smaller Numbers After SelfComing soonPer-element inversion count — merge sort with index tracking or a Fenwick tree.
- Reverse PairsComing soonCount pairs with a[i] > 2·a[j] — same merge-sort counting with a modified condition.
- Sort an ArrayComing soonImplement merge sort itself, the engine behind the O(n log n) inversion count.
- Global and Local InversionsComing soonCompare total inversions to adjacent inversions — a direct inversion-counting application.