Interactive demo
Bubble Sort Visualization
Bubble sort walks through the array again and again and swaps every pair of neighbors that is in the wrong order. It is simple, but with O(n²) steps one of the slowest sorting algorithms.
Choose “Sorted” as the starting order: a single pass without swaps is enough. “Reversed” is the worst case.
Playback
- Comparisons
- 0
- Writes
- 0
Array
Legend
- Unsorted element
- Compared neighbors
- Final position
Runtime and properties
Best case
O(n)
Already sorted: one pass without a single swap ends the sort.
Average case
O(n²)
Every element moves only one place per swap, so about n²/2 comparisons are needed.
Worst case
O(n²)
Reversed order: every pass has to swap every pair it compares.
Extra memory
O(1)
Only neighbors are swapped, no extra memory is needed.
Stable
Yes
Equal neighbors are never swapped.
In-place
Yes
Elements are only swapped within the array.
n is the number of elements. O(n log n) is the best a sorting algorithm based on comparisons can achieve.
Compared with the other sorting algorithms
| Algorithm | Best case | Average case | Worst case | Extra memory | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble sort this page | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Shell sort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | No | Yes |
| Tree sort | O(n log n) | O(n log n) | O(n²) | O(n) | Yes | No |
| Tournament sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Patience sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Block sort | O(n) | O(n log n) | O(n log n) | O(1) | Yes | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
1. Compare neighbors
A pass compares every element with its right neighbor. If the left one is larger, the two are swapped.
2. The largest bubbles up
The largest element is swapped along until it reaches the end of the array, like a bubble rising in water. After every pass the unsorted part is one element shorter.
3. Stop early
If a whole pass gets by without a single swap, everything is in order and the sort can stop. That makes bubble sort fast on arrays that are already sorted.