Bubble Sort

BeginnerSorting

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm gets its name because smaller elements 'bubble' to the top of the list.

Complexity

Best	O(n)
Average	O(n^2)
Worst	O(n^2)
Space	O(1)

StableIn-place

Live stats

Step: 0 / 0
Comparisons: 0
Swaps: 0

Step 0 / 0 · Comparisons: 0 · Swaps: 0

How it works

Start with an unsorted array of numbers.
Compare the first two adjacent elements.
If the left element is greater than the right, swap them.
Move to the next pair and repeat.
After one full pass, the largest element 'bubbles' to the end.
Repeat the process for the remaining unsorted portion.
If a pass completes with no swaps, the array is sorted.

Key concepts

Comparison-based sorting
Stable sort (preserves relative order of equal elements)
In-place (O(1) extra space)
Adaptive: best case O(n) with early exit

When to use it

When the input is small or nearly sorted. Rarely used in practice for large datasets due to O(n^2) average complexity.

Did you know

The bubble sort is sometimes called 'sinking sort' because larger elements 'sink' to the bottom.