Bubble Sort

How it works

1. Walk the list from left to right, comparing each value with its right-hand neighbour.
2. If the left value is larger, swap the two.
3. After one pass the largest remaining value has 'bubbled' to the end, where it stays.
4. Repeat on the unsorted part. A pass with no swaps means the list is sorted, so stop early.

Default run (21 steps): Unsorted array: [8, 3, 5, 1, 9]. Bubble sort compares neighbours and swaps them when they are out of order. … Sorted: [1, 3, 5, 8, 9] after 10 comparisons and 5 swaps.