Bubble sort

Bubble sort is the simplest sorting algorithm to describe: compare two neighbours, swap them if they are in the wrong order, and repeat. It is slow on long lists, but every step is easy to follow, which makes it the classic first algorithm to watch.

Bars of different heights being sorted, two neighbours highlighted for a swap and the tallest bars already in place at the end
Bars of different heights being sorted, two neighbours highlighted for a swap and the tallest bars already in place at the end

The idea

Walk through the list from left to right and look at each pair of neighbours. If the left value is larger than the right one, swap them. When you reach the end, the largest value has been carried all the way to the last place, the way a bubble rises to the surface. That walk is called a pass. Repeat the passes until the list is sorted.

An example

Take 5, 1, 4, 2, 8. The first pass compares 5 and 1 and swaps them, then 5 and 4 (swap), 5 and 2 (swap), and 5 and 8 (no swap): 1, 4, 2, 5, 8. The 8 is now in its final place. The second pass compares 1 and 4 (no swap), 4 and 2 (swap) and 4 and 5 (no swap): 1, 2, 4, 5, 8. The third pass makes no swaps at all, so the list is sorted: 9 comparisons and 4 swaps.

Why each pass leaves one more value in place

During a pass, the largest value seen so far is always carried along: once the pass reaches it, every comparison moves it one more place to the right. So the first pass puts the largest value last, the second pass the second largest just before it, and so on. After pass k the last k places are final, and the next pass can stop one place earlier. That is why the passes get shorter.

Swaps equal inversions

An inversion is a pair of values that is in the wrong order: a larger value somewhere before a smaller one. Swapping two neighbours that are out of order removes exactly one inversion and creates none. So bubble sort makes exactly as many swaps as the start list has inversions, whatever order the comparisons come in. A sorted list has none; a reversed list of n values has n(n − 1)/2, the most possible.

The early stop and the cost

If a whole pass makes no swaps, every neighbour is in order and the list is sorted. Checking for that lets bubble sort finish a sorted list in a single pass of n − 1 comparisons. In the worst case it still needs n − 1 passes and n(n − 1)/2 comparisons, and on average the number of swaps is n(n − 1)/4. Both grow with n², so doubling the list makes the sort about four times as long.

Bubble sort is stable: equal values never swap, so they keep their order. It sorts in place with no extra memory. Insertion sort shares those properties and usually needs fewer steps, and merge sort and quicksort take time proportional to n log n, which is far less on long lists.

Explore it

Open the app and press Play, or press Step to go one comparison at a time. The two values being compared are highlighted, a swap is shown in its own colour, and the values already in place turn green. Try a reversed list to see the worst case, a nearly sorted one to see the early stop end the sort after a few passes, or type the numbers from the example above.

Frequently asked questions

What is the time complexity of bubble sort?

O(n²) in the worst and average case: up to n(n − 1)/2 comparisons for n values. With the early stop, a list that is already sorted takes O(n), a single pass. It needs only O(1) extra memory.

Is bubble sort stable?

Yes. It swaps two neighbours only when the left one is strictly larger, so equal values never pass each other and keep their original order.

What is the difference between bubble sort and insertion sort?

Both swap neighbours and both make as many swaps as there are inversions. Bubble sort makes full passes over the unsorted part; insertion sort slides each new value back only as far as it needs to go, so it usually makes fewer comparisons, especially on nearly sorted lists.

When is bubble sort a good choice?

Mostly for teaching, and for very short lists where simplicity matters more than speed. For anything larger, the sort built into your programming language is far faster.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try bubble sort