Bubble sort visualizer

Type a list in the box, separated by commas, spaces or new lines. Numbers are sorted by value, and words alphabetically, ignoring capitals. The sorted list appears straight away, and the animation below plays the sort one step at a time.

Play runs it, Step forward and Step back move one comparison at a time, and Speed sets the pace. Yellow bars are being compared, orange ones have just swapped, and green ones are in their final place. Show the steps lists the list after every pass. The animation takes up to 24 items.

Bubble sort walks along the list comparing each item with the one next to it. If a pair is in the wrong order, it swaps them. One walk from start to end is called a pass.

After the first pass the largest item has been carried all the way to the end, the way a bubble rises to the top, which is where the name comes from. Each pass after that can stop one place earlier, since the end of the list is already sorted. If a pass makes no swaps at all, the list is sorted and it stops.

On a list of n items in reverse order, bubble sort makes n × (n − 1) ÷ 2 comparisons: 10 for five items, 45 for ten, and nearly half a million for a thousand. Computer scientists write that as O(n²). On a list that's already sorted it needs a single pass, n − 1 comparisons.

Large items near the start move quickly, a whole pass at a time, while small items near the end creep back one place per pass. They're known as rabbits and turtles, after Aesop's fable.

The earliest description of the algorithm is in a 1956 paper by Edward Harry Friend, who called it sorting by exchange. The name bubble sort came later, from Kenneth Iverson.

Donald Knuth wrote in The Art of Computer Programming that it seems to have nothing to recommend it, except a catchy name and some interesting theoretical problems. And in a 2007 interview, Google's chief executive Eric Schmidt asked Barack Obama the best way to sort a million integers. Obama's answer: "I think the bubble sort would be the wrong way to go."