Bubble Sort

By Victor Arce

Bubble sort is the most intuitive way to put a list in order: repeatedly walk through it, compare each pair of neighbours, and swap them whenever they are out of order. After each full pass the largest remaining value has "bubbled" to the end — which is where the name comes from.

Step through it below. Each comparison and each swap is its own step, so you can move forward and backward at your own pace.

How it works

On every pass we compare positions 1 & 2, then 2 & 3, and so on. If the left value is larger than the right one, we swap them. The biggest value keeps moving right until it settles at the end; the sorted region (in green above) grows from the right with each pass.

A small optimization makes it adaptive: if a whole pass makes no swaps, the array is already sorted and we can stop early. That is why a list that is already in order finishes in a single clean pass.

Cost

Bubble sort makes on the order of n² comparisons in the average and worst case, and O(n) in the best case (already-sorted input, with early exit). It uses no extra memory (in-place) and is stable — equal values keep their original order. Those properties make it a great teaching tool, even though faster sorts are used in practice.