Bubble Sort in C++: A Practical, Deep Dive

I still reach for bubble sort when I want to teach someone what “sorting” really means in code. There’s something refreshingly concrete about watching neighboring elements compare, swap, and slowly drift into place—like people in a line bubbling toward their correct spot. If you’re new to algorithms, bubble sort is the shortest path from “I get the idea” to “I can write it.” If you’re experienced, it’s a compact testbed for discussions about stability, data movement, and early-exit checks.

You’ll learn how bubble sort actually moves values, how to implement it in clean modern C++, and where it fits in today’s toolset. I’ll show a straightforward version first, then a faster-in-practice variant that stops early when the data is already sorted. I’ll also cover real-world caveats: when bubble sort is a good choice, when it’s the wrong choice, and what mistakes I still see in production code reviews. By the end, you’ll have a couple of ready-to-run implementations plus a mental model you can reuse when you read or design other sorting routines.

The mental model: adjacent swaps and a drifting boundary

Bubble sort is a repeated pass over your data where you only compare neighbors. If they’re out of order, you swap them. That’s it. The power of the algorithm is in the repeated passes: after one full left-to-right pass, the largest element “bubbles” to the end because it keeps swapping forward whenever it meets something smaller.

I like to picture a crowd moving along a hallway. Every time two people are in the wrong order, they switch places. After one pass, the tallest person is guaranteed to be at the far right. After two passes, the two tallest are at the rightmost two positions. This creates a shrinking “unsorted” region at the front.

In code, that means you can shorten the inner loop every pass: there’s no point in comparing the last element after you already know it’s in its final position. This boundary is the key to bubble sort’s basic efficiency gain, and it’s also the simplest way to show how algorithms can get smarter with just a small change in loop bounds.

From a teaching perspective, bubble sort is my favorite way to introduce these algorithmic truths:

• Local decisions (neighbor comparisons) can lead to global order.
• Data movement is costly, so you should count swaps, not just comparisons.
• The loop bounds you choose encode algorithmic guarantees.

Baseline C++ implementation with clear intent

Here’s a straightforward C++ version that sorts a vector in ascending order. I keep it readable and explicit because bubble sort is usually introduced early, and clarity beats cleverness here.

// Bubble sort: simple, readable version
#include 
#include 
void bubble_sort(std::vector& values) {
const int n = static_cast(values.size());
// Each pass places the next-largest value at the end
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (values[j] > values[j + 1]) {
std::swap(values[j], values[j + 1]);
}
}
}
}
int main() {
std::vector values{5, 1, 4, 2, 8};
bubble_sort(values);
for (int v : values) {
std::cout << v << ' ';
}
std::cout << '\n';
return 0;
}

A few details matter in practice:

• I cast values.size() to int because I’m using integer indices and subtraction. It keeps the math simple and avoids unsigned underflow bugs.
• The inner loop stops at n - i - 1, which is the shrinking unsorted region.
• I use std::swap because it’s clear and safe for standard types.

This implementation is stable by default: equal elements retain their original relative order because we only swap when values[j] > values[j + 1]. That stability is a real feature if you’re sorting records by a secondary key later.

Early-exit improvement: stop when the data is already sorted

Bubble sort’s biggest weakness is wasted passes on data that is already sorted or nearly sorted. In real systems, that can happen more often than you’d expect—think of time-series data where each new item is appended in order. An early-exit check can reduce the work from O(n²) to roughly O(n) on already sorted input.

I add a flag that tracks whether any swap happened in a pass. If no swap happens, the array is already sorted, and we can exit.

// Bubble sort with early-exit check
#include 
#include 
void bubble_sort(std::vector& values) {
const int n = static_cast(values.size());
for (int i = 0; i < n - 1; ++i) {
bool swapped = false;
for (int j = 0; j < n - i - 1; ++j) {
if (values[j] > values[j + 1]) {
std::swap(values[j], values[j + 1]);
swapped = true; // mark that this pass did real work
}
}
if (!swapped) {
break; // already sorted
}
}
}
int main() {
std::vector values{1, 2, 3, 4, 5};
bubble_sort(values);
for (int v : values) {
std::cout << v << ' ';
}
std::cout << '\n';
return 0;
}

I still call this bubble sort, not a different algorithm, because the core behavior is unchanged: it’s still comparing neighbors and swapping. The early-exit flag just avoids redundant passes. In my experience, this small change is the first “aha” moment when readers see how an algorithm can respond to its input.

Generalizing bubble sort without losing clarity

Once you understand the basic algorithm, you can extend it to sort other types or custom orderings. The trick is to keep the code honest: bubble sort is already O(n²), so I don’t add unnecessary abstraction that could hide costs.

Here’s a simple template that accepts a comparator. I keep the comparator inline and default to std::less so you can sort ascending without extra ceremony.

// Bubble sort with a comparator
#include 
#include 
#include 
#include 
template <typename T, typename Compare = std::less>
void bubble_sort(std::vector& values, Compare comp = Compare{}) {
const int n = static_cast(values.size());
for (int i = 0; i < n - 1; ++i) {
bool swapped = false;
for (int j = 0; j < n - i - 1; ++j) {
if (comp(values[j + 1], values[j])) {
std::swap(values[j], values[j + 1]);
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
struct Ticket {
std::string title;
int priority; // higher means more urgent
};
int main() {
std::vector tickets{
{"Login issue", 2},
{"Billing error", 5},
{"UI request", 1}
};
// Sort descending by priority
bubble_sort(tickets, [](const Ticket& a, const Ticket& b) {
return a.priority > b.priority;
});
for (const auto& t : tickets) {
std::cout << t.title << ": " << t.priority << '\n';
}
return 0;
}

Notice that I compare values[j + 1] against values[j] via the comparator. That keeps the “swap if out of order” logic consistent across ascending or descending orderings. It also preserves stability when the comparator returns false for equal items.

This style reads clearly and matches how you’d reason about order in modern C++: “swap if the right-hand element should come before the left-hand one.” It’s a small shift in perspective that pays off when you later use std::sort, std::stable_sort, or std::ranges::sort.

A step-by-step walkthrough on a tiny array

If you’re new to bubble sort, a full walk-through is worth the time. Let’s sort [5, 1, 4, 2, 8] in ascending order.

Pass 1:

• Compare 5 and 1 → swap → [1, 5, 4, 2, 8]
• Compare 5 and 4 → swap → [1, 4, 5, 2, 8]
• Compare 5 and 2 → swap → [1, 4, 2, 5, 8]
• Compare 5 and 8 → no swap → [1, 4, 2, 5, 8]

Largest value (8) is at the end. The last index is now “done.”

Pass 2:

• Compare 1 and 4 → no swap
• Compare 4 and 2 → swap → [1, 2, 4, 5, 8]
• Compare 4 and 5 → no swap

Now 5 is in its final spot. The last two indices are “done.”

Pass 3:

• Compare 1 and 2 → no swap
• Compare 2 and 4 → no swap

No swaps this pass, so we can early-exit. The array is sorted.

That example shows two important invariants:

• After the k-th pass, the last k elements are guaranteed to be in their final positions.
• A swap-free pass means the whole array is sorted, not just the last section.

Those invariants are the reason the loop bounds and the early-exit flag are correct.

Stability: why it matters and how bubble sort keeps it

Stability is one of those properties people gloss over until it bites them. A stable sort keeps equal elements in their original order. Imagine a list of customer tickets sorted by “priority,” but within the same priority you want older tickets first. If your sort is unstable, those older tickets can jump around and confuse your downstream logic.

Bubble sort is stable if—and only if—you swap when the left item is strictly greater than the right item. If you swap on “greater than or equal,” you’ll shuffle equals and break stability.

Here’s a tiny example using pairs:

• Original: (priority 2, created 10:01), (priority 2, created 09:59)
• If you swap on >=, the order can reverse.
• If you swap only on >, the earlier record stays earlier.

When I teach this, I make the stability rule explicit, because it’s an easy line to accidentally cross in a refactor.

Edge cases you should handle explicitly

Bubble sort is simple, but edge cases are still real. A few you should test:

• Empty array: no passes; function should return immediately.
• Single element: already sorted; no swaps; early-exit should trigger.
• All equal elements: should remain stable and skip extra passes.
• Reverse-sorted array: worst case; should do maximum swaps.
• Duplicate-heavy array: watch stability; test that equal items keep their order.

For safety and readability, I often add a tiny early guard in generic versions:

if (values.size() < 2) return;

It makes the loop logic simpler and avoids the n - 1 math for edge cases.

Instrumenting bubble sort: counting comparisons and swaps

If you want practical intuition, instrument the algorithm. Count how many comparisons and swaps occur for different inputs. You’ll see O(n²) quickly, and you’ll see how the early-exit flag changes the story for already-sorted data.

Here’s a compact instrumented version:

#include 
#include 
struct SortStats {
long long comparisons = 0;
long long swaps = 0;
};
SortStats bubble_sort(std::vector& values) {
SortStats stats;
const int n = static_cast(values.size());
if (n < 2) return stats;
for (int i = 0; i < n - 1; ++i) {
bool swapped = false;
for (int j = 0; j < n - i - 1; ++j) {
++stats.comparisons;
if (values[j] > values[j + 1]) {
std::swap(values[j], values[j + 1]);
++stats.swaps;
swapped = true;
}
}
if (!swapped) break;
}
return stats;
}
int main() {
std::vector values{5, 1, 4, 2, 8};
SortStats stats = bubble_sort(values);
for (int v : values) std::cout << v << ' ';
std::cout << "\nComparisons: " << stats.comparisons
<< ", swaps: " << stats.swaps << '\n';
return 0;
}

Run this on a sorted array versus a reverse-sorted array. You’ll see:

• Sorted: comparisons ≈ n-1 + n-2 + … until the early exit hits (often just one pass).
• Reverse: swaps are almost as many as comparisons, because every pair is inverted.

That data tells a story. Bubble sort doesn’t just “do O(n²).” It does it because it has no way to jump over distant inversions. It only fixes problems one adjacent swap at a time.

Time, space, and practical performance expectations

Bubble sort is O(n²) in the average and worst case because each pass can compare almost every adjacent pair. Even with the early-exit check, the worst case remains O(n²). Space is O(1) because it sorts in place.

In practice, bubble sort can feel “fast enough” for tiny datasets, but it falls off quickly as the data grows. On modern hardware, I typically see these ranges when the implementation is straightforward and compiled with standard settings:

• About 10–15 ms for arrays around a few thousand elements.
• Around 100–200 ms for arrays around ten thousand elements.
• Past that, the time can climb into seconds.

These ranges vary based on data distribution and compiler flags, but they’re good enough for decision-making. I use bubble sort only when one of these is true:

• The array is very small (dozens of elements, not thousands).
• The array is already sorted most of the time, and I want a stable, early-exit behavior without relying on more complex code.
• I’m teaching or debugging algorithmic behavior.

Here’s a short decision guide I share with teams:

• If you’re sorting user-facing data or production arrays over a few hundred items, use std::stable_sort or std::sort.
• If you’re sorting in a tight loop inside a service, use std::sort and measure.
• If you need stable order with small inputs and want easy-to-read code, bubble sort with early-exit is fine.

Traditional vs modern usage patterns

Bubble sort has an educational reputation, but it still shows up in real code for tiny data. The difference now is how we wrap it: clearer types, safer indexing, and minimal surprises. Here’s how I compare the old and modern approaches.

Traditional pattern

Modern C++ pattern

—

—

Raw arrays and manual size management

std::vector with explicit size and bounds

int everywhere without casts

static_cast(size) to avoid unsigned bugs

No early-exit check

Early-exit flag for already sorted data

Hard-coded ascending order

Comparator parameter to support custom ordering

Little or no comments

Short comments where logic isn’t obviousI still avoid overengineering. Bubble sort is most valuable when it’s small and readable. If you wrap it in heavy templates or add extra layers of indirection, you lose that clarity and you’re not gaining performance.

Common mistakes I see (and how to avoid them)

I review a lot of beginner-friendly code, and the same issues appear again and again. Here are the ones worth avoiding right away.

1) Wrong inner loop bound

If you use j < n - 1 instead of j < n - i - 1, you compare elements that are already in their final positions. It still works but wastes time. Stick to the shrinking boundary.

2) Unsigned underflow

Writing for (sizet i = 0; i < n - 1; ++i) when n is sizet can underflow if n is 0. I either check if (n < 2) return; or cast n to int up front. Both are fine; just be consistent.

3) Unstable swaps

If you swap when values[j] >= values[j + 1] instead of strictly >, you lose stability. That can break downstream behavior if you’re sorting records with equal keys.

4) Hidden cost from copies

Sorting large objects by value is expensive. If you’re sorting records or structs, prefer storing them in a vector and swapping by value, or consider sorting indices instead. Bubble sort does many swaps; heavy objects make that worse.

5) Misusing bubble sort for large data

This one is the most painful. Bubble sort is not a general-purpose production sorter. If your dataset is in the tens of thousands or more, I recommend switching to std::sort or std::stable_sort and moving on.

How bubble sort compares to other simple sorts

Bubble sort lives in a family of “teachable” sorts. It’s helpful to see how it stacks up against its peers.

• Selection sort: Finds the smallest element and swaps it into place each pass. Still O(n²), fewer swaps than bubble sort, not stable by default.
• Insertion sort: Builds a sorted prefix by inserting each new element in the right spot. O(n²) worst case, but very fast on nearly sorted data and usually the best “small data” option.
• Bubble sort: Swaps neighbors until order emerges. Easiest to visualize, stable, and quick to implement.

If I have to choose a simple algorithm for tiny inputs in real code, I tend to pick insertion sort because it has better performance on nearly sorted data. But bubble sort is the clearest when the goal is understanding or step-by-step debugging.

A realistic scenario: sorting a handful of records

Here’s an example that looks like real work. Suppose you have a small list of build tasks and want to sort by priority while keeping the original order for ties.

#include 
#include 
#include 
struct Task {
std::string name;
int priority;  // lower is higher priority
int index;     // original position, used for sanity checks
};
template 
void bubble_sort(std::vector& values, Compare comp) {
const int n = static_cast(values.size());
if (n < 2) return;
for (int i = 0; i < n - 1; ++i) {
bool swapped = false;
for (int j = 0; j < n - i - 1; ++j) {
if (comp(values[j + 1], values[j])) {
std::swap(values[j], values[j + 1]);
swapped = true;
}
}
if (!swapped) break;
}
}
int main() {
std::vector tasks{
{"lint", 2, 0},
{"build", 1, 1},
{"test", 1, 2},
{"deploy", 3, 3}
};
bubble_sort(tasks, [](const Task& a, const Task& b) {
return a.priority < b.priority; // ascending priority
});
for (const auto& t : tasks) {
std::cout << t.name << " (p" << t.priority
<< ", idx " << t.index << ")\n";
}
return 0;
}

Because the comparator only returns true when the right-hand element should come before the left-hand one, equal priorities keep their original order. That’s stability in practice.

When bubble sort is a good choice

Bubble sort isn’t “bad,” it’s just limited. I still use it in these scenarios:

• Tiny config lists: A UI settings list with 10–20 entries that changes rarely.
• Teaching: Showing the effect of swaps and pass-by-pass ordering.
• Debugging: When I want a sorting method that’s easy to step through in a debugger.
• Nearly sorted streams: When data arrives in mostly sorted order and I want a stable, predictable routine without external dependencies.

If you’re working with modern C++ in 2026, there’s also a workflow advantage: a small, readable algorithm can be easier to review with AI-assisted tools. When I ask a code assistant to explain or test a bubble sort, I get precise suggestions quickly because the logic is minimal and deterministic. That’s a subtle benefit, but in fast-moving teams, clarity is a real feature.

Still, when you need speed or large data handling, use the standard library. The algorithms in are tuned and maintained with years of testing behind them. Bubble sort is a tool, not a default.

When bubble sort is the wrong choice

Knowing where not to use bubble sort is as important as knowing how it works.

Avoid bubble sort when:

• Data size is large: thousands and up, unless you measure and prove it’s fine.
• Performance is a key feature: API latency, analytics jobs, or real-time systems.
• You need cache efficiency: bubble sort does many passes and touches memory repeatedly.
• You already have a tested library option: std::sort or std::stable_sort will beat it and be more robust.

If your codebase has a well-tested utility for sorting small arrays, use that. Reinventing sorting is rarely a good investment unless teaching is the goal.

Micro-optimizations that are usually not worth it

Every bubble sort tutorial eventually adds a fancy tweak. Most of them are not worth the complexity in production code. A few examples:

• Tracking the last swap index: You can shorten the inner loop by remembering where the last swap occurred. It can save comparisons on partially sorted data, but it makes the code less readable.
• Bidirectional bubble (cocktail shaker): It bubbles the largest right and the smallest left in alternating passes. It’s still O(n²), and the added code often doesn’t justify the gain.
• Manual unrolling: This usually makes the code harder to read and doesn’t help much unless you’re doing micro-benchmarks.

The one optimization I do recommend is the early-exit flag. It’s a clean, easy win that doesn’t complicate the algorithm or mislead readers.

Memory movement: why bubble sort is swap-heavy

Bubble sort does a lot of swaps. That’s not just a constant factor; it matters if elements are large or if swaps are expensive. Each swap can involve multiple copies or moves. If your vector contains large structs, bubble sort may become much slower than a sort that minimizes moves.

Two ways to reduce the cost:

• Sort indices instead: Keep a vector of indices and sort that by comparing the underlying data. You still do many swaps, but swaps of integers are cheap.
• Use move-aware swaps: For custom types, ensure moves are cheap and safe so that std::swap is efficient.

That said, if you are already at the stage where swap cost matters, you should probably stop using bubble sort.

A compact version for interview practice

Sometimes you need a short, clear implementation for an interview or an exercise. This version is minimal but correct, with an early-exit check.

void bubble_sort(std::vector& a) {
const int n = static_cast(a.size());
if (n < 2) return;
for (int i = 0; i < n - 1; ++i) {
bool swapped = false;
for (int j = 0; j < n - i - 1; ++j) {
if (a[j] > a[j + 1]) {
std::swap(a[j], a[j + 1]);
swapped = true;
}
}
if (!swapped) break;
}
}

If asked about complexity, I keep it short:

• Time: O(n²) worst case, O(n) best case with early-exit
• Space: O(1) extra space
• Stable: yes, if swap condition is strict >

Understanding correctness: a simple proof sketch

Correctness proofs sound intimidating, but bubble sort has an easy one. I use this sketch:

1) Invariant after each pass: After pass i (0-based), the last i elements are in final sorted position.

2) Reason: The largest element in the unsorted region will be swapped rightward until it reaches the end of that region. That happens because it is greater than each neighbor it meets, so it keeps moving right.

3) Termination: After n-1 passes, all elements have been placed.

4) Early-exit: If a pass makes no swaps, every adjacent pair is already in order, which implies the whole array is sorted.

This reasoning is useful because it also hints at how other algorithms work: define an invariant, show it’s preserved, show it leads to the goal.

Performance considerations: comparisons, swaps, and branch behavior

When bubble sort runs on modern CPUs, a few things influence performance:

• Branch prediction: The if inside the inner loop can be hard to predict on random data, which slows it down.
• Cache friendliness: It scans adjacent elements, which is cache-friendly, but it does many passes over the same region.
• Swap cost: For primitive types, swaps are cheap; for complex types, they can dominate.

These details matter if you’re benchmarking, but they don’t change the big picture: bubble sort is quadratic and becomes slow quickly as data grows.

Testing bubble sort in practice

If I’m adding bubble sort to a codebase (usually for educational reasons), I add a few tests:

• Sorted input: [1,2,3,4] should remain unchanged and do minimal swaps.
• Reverse input: [4,3,2,1] should sort correctly.
• Duplicates: [3,1,2,1] should be stable for equal keys.
• Empty and single: [] and [5] should remain unchanged.
• Custom comparator: Sorting objects by a field should work and keep stability for ties.

Even simple algorithms deserve tests. It’s a good habit and a good way to catch the exact mistakes listed earlier.

Alternative approaches: when you want the same goal with better performance

If your real goal is “sort a small array quickly,” the main alternatives are:

• Insertion sort: Often faster on nearly sorted data and still easy to implement.
• Library sort: std::sort (fast, not stable) or std::stable_sort (stable, a bit slower).
• Partial sorting: If you only need the top k elements, use std::partial_sort or a heap.

The bigger point is this: bubble sort is about clarity. When clarity is no longer the priority, the standard library should take over.

AI-assisted workflows: how bubble sort helps learning tools

When I use AI tools for code review or tutoring, bubble sort is a great example because it’s small and deterministic. That means:

• The tool can generate test cases quickly.
• Explanations are consistent because there are few branches.
• It’s easy to ask “why does this swap happen?” and get a precise answer.

If you’re mentoring or learning, bubble sort is a friendly playground for asking questions like “What does stability mean?” or “How does early exit change complexity?” The algorithm is small enough that you can understand the full mental model in one sitting.

A quick comparison table of simple sorts

Here’s a concise comparison you can reference:

Algorithm

Time (worst)

Best case

Stable

Notes —

—

—

—

— Bubble sort

O(n²)

O(n) with early exit

Yes

Best for teaching, tiny inputs Insertion sort

O(n²)

O(n)

Yes

Fast on nearly sorted data Selection sort

O(n²)

O(n²)

No

Few swaps, still slow

This isn’t to dismiss bubble sort. It’s to place it in the right mental shelf.

Common pitfalls in template versions

When people generalize bubble sort, they sometimes introduce subtle bugs:

• Comparator direction: If you write if (comp(values[j], values[j + 1])) you’ll swap in the wrong direction. The correct logic is “swap if right should come before left.”
• Comparator for equals: If your comparator returns true for equal items, you can break stability. Good comparators should return false for equality.
• Over-template for no reason: Templates are great when you need them, but for teaching, a simple vector is better.

I keep these in mind when I review student code because they’re easy to miss in casual testing.

A mental shortcut for remembering loop bounds

If you ever forget the n - i - 1 bound, remember this:

• After pass i, the last i elements are settled.
• The last index you need to compare against is n - i - 2 (because you compare j with j+1).
• So the loop condition is j < n - i - 1.

This tiny reasoning helps prevent off-by-one errors, which are the most common bug in beginner implementations.

Putting it all together: a final reference implementation

Here’s a polished reference version I use in notes. It’s short, safe, and stable, with early exit and a comparator.

#include 
#include 
template <typename T, typename Compare = std::less>
void bubble_sort(std::vector& values, Compare comp = Compare{}) {
const int n = static_cast(values.size());
if (n < 2) return;
for (int i = 0; i < n - 1; ++i) {
bool swapped = false;
for (int j = 0; j < n - i - 1; ++j) {
if (comp(values[j + 1], values[j])) {
std::swap(values[j], values[j + 1]);
swapped = true;
}
}
if (!swapped) break;
}
}

If you only remember one version, make it this one. It’s clear, stable, early-exiting, and easy to adapt.

Final thoughts

You now have the full picture: how bubble sort works, how to code it cleanly in C++, and how to decide when it fits. If you want a short next step, I recommend two small exercises. First, take the comparator-based version and sort a list of records by two keys (e.g., priority then name) while preserving stability. Second, instrument the code to count comparisons and swaps, then run it on sorted, reverse-sorted, and random inputs. You’ll feel the O(n²) behavior in the numbers, and that intuition will carry into every other sorting discussion you have.

When I teach this algorithm, I focus on the habits it builds: clear loop bounds, small local invariants, and the discipline to measure cost. Those habits matter even more than the algorithm itself. If you can read a bubble sort and explain why it works, you can do the same for insertion sort, selection sort, and eventually the faster divide-and-conquer sorts you’ll rely on in production. Keep the code simple, keep the mental model tight, and choose the tool that fits the data you really have.