Bubble Sort

Bubble sort compares adjacent pairs of elements and swaps them if they are in the wrong order. It repeats this process across multiple passes through the list until no more swaps are needed and the list is fully sorted.

The name comes from the effect each pass has: the largest unsorted element gradually "bubbles up" to its correct position at the end of the list.

After each pass, the next-largest unsorted element settles into its final position. After k passes, the k largest elements are in their correct positions at the end.

Rules for each comparison:

• Compare the element at position $i$ with the element at position $i+1$
• If they are in the wrong order (left > right), swap them
• Move on to the next pair
• Repeat until the end of the unsorted region

For a list of $n$ elements, at most $n-1$ passes are needed.

Sort [5, 3, 8, 1, 4] using bubble sort.

Starting with the full list, pass 1 makes $n-1=4$ comparisons:

Step	Comparison	Swap?	List after step
1	5 vs 3	Yes	[3, 5, 8, 1, 4]
2	5 vs 8	No	[3, 5, 8, 1, 4]
3	8 vs 1	Yes	[3, 5, 1, 8, 4]
4	8 vs 4	Yes	[3, 5, 1, 4, 8]

After pass 1: [3, 5, 1, 4, 8]

The value 8 — the largest element — has reached its final position at the end. It will not be compared again in future passes.

Write carries and swaps explicitly in exams. Do not attempt to track multiple swaps mentally.

Continuing with [3, 5, 1, 4, 8]. Each pass shortens the unsorted region by one element.

Pass 2 (3 comparisons — position 4 is already sorted):

Step	Comparison	Swap?	List after step
1	3 vs 5	No	[3, 5, 1, 4, 8]
2	5 vs 1	Yes	[3, 1, 5, 4, 8]
3	5 vs 4	Yes	[3, 1, 4, 5, 8]

Remaining passes (summary):

After pass	List state	Sorted region
1	[3, 5, 1, 4, 8]	last 1 element
2	[3, 1, 4, 5, 8]	last 2 elements
3	[1, 3, 4, 5, 8]	last 3 elements
4	[1, 3, 4, 5, 8]	fully sorted

Pass 3 details: compare 3 vs 1 (swap → [1, 3, 4, 5, 8]), compare 3 vs 4 (no swap). Pass 4: compare 1 vs 3 (no swap). List is now sorted.

Without any optimisation, bubble sort always runs exactly $n-1$ passes — even on a list that is already sorted.

The swap flag fixes this. At the start of each pass, set a flag to False. If any swap occurs during that pass, set it to True. At the end of the pass:

• If the flag is still False → no swaps occurred → the list is already sorted → exit early
• If the flag is True → at least one swap occurred → run another pass

swapped ← True
endIndex ← n - 2
WHILE swapped = True
    swapped ← False
    FOR i ← 0 TO endIndex
        IF list[i] > list[i + 1] THEN
            swap(list[i], list[i + 1])
            swapped ← True
        END IF
    END FOR
    endIndex ← endIndex - 1
END WHILE

Example on an already-sorted list [1, 2, 3, 4, 5]:

Pass 1: 1 < 2 (no swap), 2 < 3 (no swap), 3 < 4 (no swap), 4 < 5 (no swap). Flag stays False → exit.

Only 1 pass and 4 comparisons are needed — not 4 passes and 10 comparisons. This makes the optimised best case O(n).

The number of comparisons in the worst case follows a predictable pattern. Each pass compares one fewer pair than the last:

Pass	Comparisons made
1	$n-1$
2	$n-2$
3	$n-3$
…	…
$n-1$	1

Total comparisons = $(n-1)+(n-2)+\dots +1=\frac{n(n-1)}{2}$

For small $n$ this is manageable. For large $n$ it becomes impractical:

$n$	Maximum comparisons
5	10
10	45
100	4,950
1,000	499,500
10,000	~50,000,000

Since $\frac{n(n-1)}{2}\approx \frac{n^2}{2}$, the complexity is written as $O(n^2)$ — doubling the list size quadruples the number of comparisons.

Best case (optimised, already-sorted list): $O(n)$ — one pass, no swaps detected. Worst case (reverse-sorted list): $O(n^2)$.

Both algorithms sort a list, but they differ significantly in performance and memory use.

Property	Bubble sort	Merge sort
Worst-case complexity	$O(n^2)$	$O(n\log n)$
Best-case complexity	$O(n)$ (optimised, with flag)	$O(n\log n)$
Extra memory required	None — sorts in place	Yes — sub-lists during merge
For $n=100$	up to 4,950 comparisons	~664 comparisons
For $n=10,000$	up to ~50,000,000 comparisons	~133,000 comparisons

When bubble sort is preferred:

• The list is very small — the overhead difference is negligible
• The list is nearly sorted — the swap flag exits after very few passes
• Memory is severely constrained — merge sort needs additional space proportional to $n$

For large unsorted datasets, merge sort is generally the better choice. The gap widens rapidly as $n$ grows.

1. Stopping after one pass

Bubble sort requires multiple passes. After one pass, only the largest element is guaranteed to be in its final position. The remaining elements may still be out of order.

2. Confusing the direction of bubbling

Each pass moves the largest unsorted element to the right (the end). Elements do not bubble to the left. If you are sorting in ascending order, the sorted region grows at the right end of the list.

3. Not reducing the comparison range each pass

After pass $k$, the last $k$ elements are sorted and need not be compared again. The inner loop shortens by one each pass. Comparing already-sorted elements wastes steps and can cost marks in a trace question.

4. Forgetting to describe the swap flag when asked about the optimised version

The optimisation is not just "stop when sorted" — the mechanism is a boolean flag set to False at the start of each pass and updated to True on any swap. If the flag remains False at the end of a pass, the algorithm terminates. Describing it vaguely as "it stops early" is not sufficient.

5. Claiming bubble sort always uses less memory than merge sort

Bubble sort is in-place and uses constant extra memory, which is an advantage. But this does not mean bubble sort is generally better — merge sort's $O(n\log n)$ performance far outweighs its memory cost for any large dataset.