Bubble sort, explained

Bubble sort is often the first sorting algorithm people learn. It walks along the list, compares each pair of neighbours and swaps them when the left one is bigger than the right one.

After one pass the largest value has "bubbled" to the end. Each further pass fixes the next largest value.

How it works

• Compare the first two items. If the left one is bigger, swap them.
• Move one position to the right and repeat until the end of the list.
• Start again from the beginning. The last item is already in place, so each pass can stop one position earlier.
• If a whole pass makes no swaps, the list is sorted and you can stop.

A small example

Sort this list:

5 1 4 2 8

After pass 1:  1 4 2 5 8
After pass 2:  1 2 4 5 8
Pass 3 makes no swaps, so it is done.

What to know about its cost

• Best case O(n) when the list is already sorted, because the early stop kicks in.
• Average and worst case O(n²).
• Uses O(1) extra space and is stable: equal items keep their order.

Where it works well

• Very easy to understand and to write.
• Fast on a list that is already nearly sorted.

Where it struggles

• Far too slow for long lists.
• Does many more swaps than other simple sorts.

Try it yourself

Open the Sorting experiment, enter the list 5 1 4 2 8, choose Bubble Sort and step through it. Then use the comparison view to run another algorithm on the same list and compare the comparisons and swaps.

Open the Sorting experiment