Bubble Sort is one of the simplest sorting algorithms and often the first one people learn. The idea is straightforward: repeatedly compare adjacent elements and swap them if they are in the wrong order. With each pass, the largest unsorted element “bubbles up” to its correct position.

While Bubble Sort is not efficient for large inputs, it plays an important role in building intuition. It helps you understand how sorting works step by step, how swaps affect order, and how repeated passes gradually lead to a sorted array.

In this chapter, you will learn how Bubble Sort works, how to implement it, and how small optimizations can improve its performance. More importantly, you will use it as a stepping stone to understand 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, much like a bubble rising to the surface of water. That is where the name comes from.

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"?

The analogy is simple. 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.

Let us break down the algorithm step by step.

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

Here is the algorithm as a flowchart:

There are two things worth noting in this flowchart. First, 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. Second, the swapped flag is reset at the start of every pass, so it tracks whether any work was done in the current pass only.

All six implementations follow the same structure: 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. The only differences are language syntax.

Let us trace through bubble sort with the array [5, 3, 8, 4, 2]. We will track every comparison and swap so you can see exactly how the algorithm progresses.

Notice how the inner loop range shrinks with each pass. In pass 1 we made 4 comparisons, in pass 2 we made 3, then 2, then 1. The total number of comparisons is 4 + 3 + 2 + 1 = 10, which is n(n-1)/2 for n=5. This is exactly where the O(n^2) comes from.

Now let us look at the best-case scenario. If the input were already sorted, say [1, 2, 3, 4, 5]:

This is why the swapped flag matters so much. Without it, bubble sort would still run all n-1 passes, doing n(n-1)/2 comparisons for an already sorted array. With it, the best case drops to O(n).

Stability: Bubble sort is a stable sorting algorithm. Two elements with equal values are never swapped (because the condition is strictly greater than, not greater-than-or-equal). This means equal elements maintain their original relative order after sorting.

In-place: Bubble sort does not require any additional arrays or data structures. All swaps happen within the original array, making the space complexity O(1).

To put the numbers in perspective, for an array of 10,000 elements:

That is a 5,000x difference, which is why the early termination optimization is not just a nice-to-have. It fundamentally changes the algorithm's behavior on nearly sorted data.

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

Good use cases:

Bad use cases:

A useful rule of thumb: if someone asks you about bubble sort in an interview, they are probably testing whether you understand its properties (stability, in-place, best case O(n)) and whether you can articulate why better alternatives exist. They are not asking you to advocate for using it in production.