Bubble Sort Explained

Bubble sort repeatedly steps through a list, compares each pair of adjacent elements, and swaps them if they are in the wrong order. With each full pass, the largest remaining value "bubbles up" to its correct position at the end. It is the simplest sorting algorithm to understand, which makes it a great teaching tool — but its O(n2) running time makes it impractical for large data.

How a pass works

Imagine scanning left to right. You compare positions 0 and 1; if the left is bigger, you swap. Then 1 and 2, then 2 and 3, and so on. By the end of one pass, the single largest element has been carried all the way to the last slot. The next pass does the same for the remaining unsorted portion, which is now one shorter. After at most n - 1 passes, everything is in order.

Bubble sort in C++

#include <iostream>
using namespace std;

// Sort the array in ascending order using bubble sort.
// Worst and average case: O(n^2). Best case (already sorted): O(n).
void bubbleSort(int arr[], int n) {
    for (int pass = 0; pass < n - 1; pass++) {
        bool swapped = false; // track whether this pass changed anything

        // After `pass` passes, the last `pass` elements are already sorted,
        // so we only scan up to n - 1 - pass.
        for (int i = 0; i < n - 1 - pass; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]); // swap out-of-order neighbours
                swapped = true;
            }
        }

        // If a whole pass made no swaps, the array is already sorted.
        // This early exit gives O(n) on nearly sorted input.
        if (!swapped) break;
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " "; // prints: 1 2 5 5 6 9
    }
    return 0;
}

The nested loops are the heart of the cost: roughly n passes each doing up to n comparisons, which is O(n2).

Why it is slow

Because every pass compares neighbours and may swap, the total number of comparisons grows with the square of the input size. Doubling the array quadruples the work. For a thousand elements that is around a million comparisons; for a million elements it becomes a trillion — far too slow. Algorithms like merge sort and quick sort reach O(n log n) and leave bubble sort far behind on large inputs.

The one optimisation worth knowing

The swapped flag matters. If a full pass makes no swaps, the array is already sorted and you can stop early. This makes bubble sort O(n) in the best case — already-sorted or nearly-sorted input. That single property is the main reason bubble sort is not entirely useless: for small or almost-ordered lists, it is simple and adaptive.

When bubble sort is acceptable

Bubble sort is fine for teaching, for tiny inputs where simplicity beats speed, and for nearly sorted data where the early exit kicks in. It is also stable (it preserves the relative order of equal elements) and sorts in place (no extra array). But for any sizeable, unordered data set, choose a faster algorithm.

Common mistakes

• Skipping the early-exit flag. Without the swapped check, bubble sort always does the full O(n2) work even on sorted input. The flag is what makes it adaptive.
• Wrong loop bounds. Comparing arr[i] and arr[i + 1] means the inner loop must stop at n - 1 - pass, not n. Going one too far reads past the array.
• Forgetting the shrinking range. Each pass fixes one more element at the end. Not shrinking the inner loop wastes comparisons re-checking sorted elements.
• Using it on large data. Bubble sort on big inputs is a performance trap. Reach for an O(n log n) algorithm instead.
• Assuming it is unstable. Bubble sort only swaps strictly out-of-order pairs, so equal elements keep their order — it is stable. Swapping on >= would break that.

FAQ

Is bubble sort ever the right choice? For very small arrays or nearly sorted data with the early-exit optimisation, yes. For general large-scale sorting, no — use merge sort or quick sort.

Is bubble sort stable and in place? Yes to both. It uses no extra array and preserves the order of equal elements.

Keep learning

Compare with Insertion & Selection Sort, then step up to the faster Merge Sort. Ground the cost analysis with Big-O Notation, and browse the full DSA hub.

Want to work through sorting algorithms with instructor feedback in Jalgaon? Join the waitlist for our Data Structures & Algorithms course.