How Does Bubble Sort Work?

Bubble sort repeatedly compares adjacent items and swaps them when they are in the wrong order. After each complete pass, the largest unsorted item has moved, or “bubbled,” to its correct position at the end of the unsorted section.

The Reasoning and Mechanism

To sort [5, 3, 8, 2] into ascending order, begin at the start and compare each adjacent pair.

After pass 1, 8 is fixed in its final position. Each later pass can therefore ignore one more item at the end. The algorithm stops when a pass produces no swaps, because this means every adjacent pair is already ordered.

One possible pseudocode implementation is:

endIndex = length(values) - 1
swapped = true

while swapped = true
    swapped = false
    for index = 0 to endIndex - 1
        if values[index] > values[index + 1]
            swap values[index], values[index + 1]
            swapped = true
        end if
    next index
    endIndex = endIndex - 1
end while

Bubble sort performs repeated comparison and swap operations. Its average-case and worst-case time complexity are $O(n^2)$, making it inefficient for large lists. With the swapped flag, its best-case complexity is $O(n)$ when the list is already sorted. It can operate in place, so it requires only constant additional memory, $O(1)$.

Exam Technique

For an IB trace question, show the list after every full pass, not only after individual swaps. A common misconception is that one pass sorts the entire list; one pass guarantees only that the largest remaining item reaches its final position. When explaining efficiency, identify the input size $n$ and state both the relevant case and time complexity.