Bubble Sort is one of the simplest sorting algorithms and is usually the first one taught in an algorithms course. It is not efficient for large inputs, but it is a useful starting point for building sorting intuition. It shows how sorting works step by step, how swaps affect order, and how repeated passes gradually lead to a sorted array.

This chapter covers how Bubble Sort works, how to implement it, and how a small optimization changes its behavior on nearly sorted data. It also serves as a stepping stone for understanding why more advanced sorting algorithms are needed.

Bubble sort is a comparison-based sorting algorithm that works by repeatedly stepping through the array, comparing adjacent elements, and swapping them if they are in the wrong order. Each pass through the array moves the largest unsorted element to its correct position at the end.

Here is the core intuition: after the first pass, the largest element is guaranteed to be at the last position. After the second pass, the second-largest element is in its correct spot. After n-1 passes, the entire array is sorted.

Example

The element 8, being the largest, bubbles to the far right after the first pass. In the next pass, 5 will bubble to its correct position (second from the right), and so on. Each pass guarantees that one more element is sorted.

Why "Bubble"?

In a carbonated drink, larger bubbles rise to the surface faster. In bubble sort, larger values rise (move toward the end of the array) faster because they keep getting swapped forward with every comparison.

The algorithm has seven steps:

Step 7 is the optimization that makes bubble sort practical on nearly sorted data. Without it, the algorithm runs n-1 passes even if the array becomes sorted after the second pass. With early termination, a pass that completes with zero swaps signals that the array is already in order, so the algorithm can stop immediately.

Here is the algorithm as a flowchart:

The flowchart highlights two details. The inner loop range shrinks by one after each pass (n-i-2 instead of n-2) because the last i elements are already sorted. The swapped flag resets at the start of every pass, so it tracks whether any work was done in the current pass only.

The implementation has three parts: an outer loop that counts passes, an inner loop that does comparisons and swaps within a pass, and an early termination check at the end of each pass.

Stability

Bubble sort is stable. The swap condition uses strict greater-than (arr[j] > arr[j+1]), so two elements with equal values are never swapped. Equal elements retain their original relative order after sorting.

This matters when sorting records by a secondary key while preserving the order from a previous primary-key sort. For example, sorting employees by salary after first sorting by name produces employees grouped by salary, with each salary group still in name order.

For an array of 10,000 elements, the gap between inputs is large:

The early termination check is what creates the best case. On an already sorted array, the swapped flag stops the algorithm after one pass of about 10,000 comparisons. Without the flag, the same input would still run all n-1 passes and do n(n-1)/2, roughly 50,000,000 comparisons. That is a 5,000x reduction in work on input that is already in order.

Bubble sort is rarely the right choice for production code, but it does have legitimate use cases.

Good Use Cases

Poor Use Cases

The value of bubble sort is conceptual. Its simplicity makes it a good place to see what stability, in-place sorting, and a best case of O(n) actually mean, and understanding why faster algorithms exist starts with understanding why this one is slow.