The Idea
Bubble Sort is the algorithm everyone meets first — and for good reason. You walk through the array, compare each pair of adjacent elements, and swap them if they're out of order. Repeat until the array is sorted. The name comes from the way large values "bubble" up to the end of the array on each pass, the same way a bubble of air rises through a glass of water. It is not the fastest sort, but it is the easiest to understand and the easiest to implement correctly.
How It Works
On each pass, bubble sort compares index i and i+1 and swaps them if they're in the wrong order. After the first full pass, the largest element is guaranteed to be in its final position at the end. After pass k, the largest k elements are locked in at the right side of the array.
After the first pass, 5 has bubbled all the way to the right. The next pass only needs to look at indices 0..3, since the last slot is already correct.
The Algorithm
- Repeat the outer loop up to
N - 1times. - On each outer iteration, walk left-to-right through the unsorted portion comparing adjacent pairs.
- If
arr[i] > arr[i+1], swap them. - Track whether any swap happened on this pass — if none did, the array is already sorted and we can stop early.
- After the loop ends, the array is sorted.
Trace Through an Example
Running bubble sort on [5, 2, 4, 1, 3]:
| Step | Action | Array State |
|---|---|---|
| Start | initial array | [5, 2, 4, 1, 3] |
| Pass 1 | swap (5,2), (5,4), (5,1), (5,3) | [2, 4, 1, 3, 5] |
| Pass 2 | swap (4,1), (4,3); 4 settles | [2, 1, 3, 4, 5] |
| Pass 3 | swap (2,1); 3 stays | [1, 2, 3, 4, 5] |
| Pass 4 | no swaps — early exit triggers | [1, 2, 3, 4, 5] |
| Done | array is sorted | [1, 2, 3, 4, 5] |
Notice how the right edge fills in with sorted values one by one — that's the "bubbling" in action.
Complexity
| Case | Time | Why |
|---|---|---|
| Best | O(N) | already sorted — one pass with no swaps, early exit |
| Average | O(N²) | roughly N/4 swaps per pass, N passes |
| Worst | O(N²) | reverse-sorted array, every comparison swaps |
| Space | O(1) | in-place, only a single temp variable |
The early-exit optimization is what saves bubble sort from being completely useless: on already-sorted (or nearly-sorted) input, it runs in linear time — the same order as just reading the array.
When Should You Use It?
- Use it when the input is small (say, fewer than ~20 elements) or you know the data is almost sorted and you want a simple, in-place pass to clean it up.
- Use it as a teaching tool — it makes the concept of "swap and compare" concrete in a way fancier sorts don't.
- Don't use it in production for any non-trivial array. Merge sort, quick sort, and Python's built-in Tim Sort all run in O(N log N).
- The transferable pattern: the idea of a pass that locks one element into its final position shows up again in selection sort, heap sort, and quickselect.