Bubble Sort Explained: How It Works, When to Use It, and Why
Sorting is one of the most fundamental operations in computing. Every time you see a leaderboard ranked by score, a contact list ordered alphabetically, or search results sorted by relevance, a sorting algorithm did that work. Understanding how sorting works under the hood is one of the first things that separates developers who just write code from developers who understand it. Bubble Sort is where that journey starts for most people — and for good reason.
Before Bubble Sort existed as a named concept, programmers faced a gnarly problem: given a random list of numbers, how do you systematically put them in order without missing anything or scrambling what you've already fixed? Bubble Sort solves this with one beautifully simple rule — repeatedly compare neighboring elements and swap them if they're in the wrong order. No element gets overlooked, and the process guarantees that after enough passes, every element is exactly where it belongs.
By the end of this article you'll be able to explain Bubble Sort out loud without looking at notes, trace through any array step-by-step on paper, write a clean working implementation in Java from memory, spot the optimized version that makes it smarter, and answer the interview questions that trip most beginners up. Let's build this from the ground up.
How Bubble Sort Actually Works — One Pass at a Time
Let's use a concrete example. Say you have this array of five numbers: [5, 3, 8, 1, 4]. Your job is to sort it smallest to largest.
Bubble Sort works in rounds called 'passes'. During each pass, you walk through the array from left to right, look at every pair of neighboring elements side by side, and ask one question: 'Is the left one bigger than the right one?' If yes, swap them. If no, move on.
After Pass 1 on [5, 3, 8, 1, 4]: - Compare 5 and 3 → 5 > 3, swap → [3, 5, 8, 1, 4] - Compare 5 and 8 → 5 < 8, no swap → [3, 5, 8, 1, 4] - Compare 8 and 1 → 8 > 1, swap → [3, 5, 1, 8, 4] - Compare 8 and 4 → 8 > 4, swap → [3, 5, 1, 4, 8]
Notice what happened: the largest number, 8, has 'bubbled up' all the way to its correct position at the end. That's the magic. Each pass guarantees the largest unsorted number finds its final home. You repeat this process, and each pass needs to go one element shorter because the last element is already locked in.
public class BubbleSortBasic { public static void main(String[] args) { // Our unsorted list of exam scores int[] scores = {5, 3, 8, 1, 4}; int numberOfScores = scores.length; System.out.println("Before sorting:"); printArray(scores); // Outer loop: controls how many passes we make. // After each pass, the largest unsorted element is in its final spot, // so we shrink the range by 1 each time (hence numberOfScores - pass - 1). for (int pass = 0; pass < numberOfScores - 1; pass++) { System.out.println("\n--- Pass " + (pass + 1) + " ---"); // Inner loop: walks through neighboring pairs in the unsorted portion. // We stop earlier each pass because the tail is already sorted. for (int index = 0; index < numberOfScores - pass - 1; index++) { // Compare the current element with the one immediately to its right if (scores[index] > scores[index + 1]) { // They're in the wrong order — swap them using a temp variable int temp = scores[index]; scores[index] = scores[index + 1]; scores[index + 1] = temp; System.out.println(" Swapped index " + index + " and " + (index + 1) + " → " + java.util.Arrays.toString(scores)); } else { System.out.println(" No swap at index " + index + " → " + java.util.Arrays.toString(scores)); } } } System.out.println("\nAfter sorting:"); printArray(scores); } // Helper method to print the array in a readable format static void printArray(int[] array) { System.out.println(java.util.Arrays.toString(array)); } }
[5, 3, 8, 1, 4]
--- Pass 1 ---
Swapped index 0 and 1 → [3, 5, 8, 1, 4]
No swap at index 1 → [3, 5, 8, 1, 4]
Swapped index 2 and 3 → [3, 5, 1, 8, 4]
Swapped index 3 and 4 → [3, 5, 1, 4, 8]
--- Pass 2 ---
No swap at index 0 → [3, 5, 1, 4, 8]
Swapped index 1 and 2 → [3, 1, 5, 4, 8]
Swapped index 2 and 3 → [3, 1, 4, 5, 8]
--- Pass 3 ---
Swapped index 0 and 1 → [1, 3, 4, 5, 8]
No swap at index 1 → [1, 3, 4, 5, 8]
--- Pass 4 ---
No swap at index 0 → [1, 3, 4, 5, 8]
After sorting:
[1, 3, 4, 5, 8]
The Optimized Version — Stop Early When the Array Is Already Sorted
The basic version has a silent problem. Imagine your array is [1, 2, 3, 4, 5] — already sorted. The basic algorithm still ploughs through all the passes anyway, making zero swaps but wasting time. With a large dataset, that's painfully inefficient.
The fix is elegant: use a flag called 'swapped'. At the start of each pass, set it to false. If you make even one swap during a pass, flip it to true. At the end of the pass, check the flag. If it's still false — meaning you walked through the entire array and didn't swap a single pair — the array is already sorted. Stop immediately.
This optimization doesn't change Bubble Sort's worst-case performance (we'll talk about that shortly), but it dramatically improves its best-case. On an already-sorted array, it now takes just one pass instead of n-1 passes. This is the version you should always write — it shows you understand the algorithm, not just the mechanics.
It also makes Bubble Sort one of the few simple algorithms that can detect a sorted array in O(n) time, which is occasionally useful in practice when you expect your data to be nearly sorted.
public class BubbleSortOptimized { public static void main(String[] args) { // Test 1: A random unsorted list of temperatures int[] temperatures = {34, 12, 45, 7, 29}; System.out.println("Test 1 — Unsorted input:"); System.out.println("Before: " + java.util.Arrays.toString(temperatures)); optimizedBubbleSort(temperatures); System.out.println("After: " + java.util.Arrays.toString(temperatures)); System.out.println(); // Test 2: An already-sorted array — watch how few passes it takes int[] alreadySorted = {1, 2, 3, 4, 5}; System.out.println("Test 2 — Already sorted input:"); System.out.println("Before: " + java.util.Arrays.toString(alreadySorted)); optimizedBubbleSort(alreadySorted); System.out.println("After: " + java.util.Arrays.toString(alreadySorted)); } static void optimizedBubbleSort(int[] array) { int size = array.length; int passCount = 0; for (int pass = 0; pass < size - 1; pass++) { // Assume no swaps have happened this pass boolean swappedThisPass = false; passCount++; for (int index = 0; index < size - pass - 1; index++) { if (array[index] > array[index + 1]) { // Swap the two neighboring elements int temp = array[index]; array[index] = array[index + 1]; array[index + 1] = temp; // At least one swap happened, so the array wasn't fully sorted yet swappedThisPass = true; } } // If we completed a full pass with zero swaps, the array is sorted. // No point continuing — exit early. if (!swappedThisPass) { System.out.println("Early exit after " + passCount + " pass(es) — array is sorted!"); return; } } System.out.println("Completed in " + passCount + " pass(es)."); } }
Before: [34, 12, 45, 7, 29]
Completed in 4 pass(es).
After: [7, 12, 29, 34, 45]
Test 2 — Already sorted input:
Before: [1, 2, 3, 4, 5]
Early exit after 1 pass(es) — array is sorted!
After: [1, 2, 3, 4, 5]
Time and Space Complexity — What the Big-O Numbers Actually Mean
Big-O notation sounds intimidating but it's just a way of asking: 'How much slower does this algorithm get as the input gets bigger?' Let's work through Bubble Sort's numbers intuitively.
Imagine you have 10 elements. In the worst case (reverse-sorted order like [10, 9, 8, 7...]), Pass 1 does 9 comparisons, Pass 2 does 8, Pass 3 does 7... all the way down to 1. Total comparisons: 9+8+7+6+5+4+3+2+1 = 45. For 100 elements that's roughly 4,950 comparisons. For 1,000 elements, about 499,500. The number of comparisons grows with the square of the input size — that's O(n²).
Bubble Sort's three cases: - Best Case O(n): Array is already sorted. With the optimized version, one pass, no swaps, done. - Average Case O(n²): Randomly ordered data. Lots of passes, lots of swaps. - Worst Case O(n²): Reverse-sorted data. Maximum comparisons and swaps every pass.
Space complexity is O(1) — constant. You're sorting the array in-place using only one temporary variable for swaps, regardless of how big the array is. That's actually a genuine strength of Bubble Sort.
For small arrays (say, fewer than 20 elements) or nearly-sorted data, Bubble Sort is perfectly fine. For large datasets, it's genuinely slow compared to Merge Sort O(n log n) or Quick Sort O(n log n) — and you'd never use it in production on big data.
public class BubbleSortComplexityDemo { // We'll count actual comparisons to verify the O(n²) claim ourselves static int comparisonCount = 0; public static void main(String[] args) { System.out.println("Demonstrating how comparison count scales with input size:\n"); System.out.printf("%-15s %-20s %-20s%n", "Array Size (n)", "Comparisons Made", "n² (theoretical)"); System.out.println("-".repeat(55)); // Test with different array sizes to show the quadratic growth int[] testSizes = {5, 10, 20, 50, 100}; for (int size : testSizes) { // Build a worst-case (reverse-sorted) array of the given size int[] reverseArray = buildReverseSortedArray(size); comparisonCount = 0; // Reset counter before each sort bubbleSortWithCounter(reverseArray); System.out.printf("%-15d %-20d %-20d%n", size, comparisonCount, (long) size * size); } System.out.println("\nNotice: actual comparisons ≈ n²/2, which is still O(n²)."); } static void bubbleSortWithCounter(int[] array) { int size = array.length; for (int pass = 0; pass < size - 1; pass++) { boolean swappedThisPass = false; for (int index = 0; index < size - pass - 1; index++) { comparisonCount++; // Count every comparison we make if (array[index] > array[index + 1]) { int temp = array[index]; array[index] = array[index + 1]; array[index + 1] = temp; swappedThisPass = true; } } if (!swappedThisPass) break; } } // Builds an array [n, n-1, n-2, ..., 2, 1] — the worst case for Bubble Sort static int[] buildReverseSortedArray(int size) { int[] array = new int[size]; for (int i = 0; i < size; i++) { array[i] = size - i; // Fills from largest to smallest } return array; } }
Array Size (n) Comparisons Made n² (theoretical)
-------------------------------------------------------
5 10 25
10 45 100
20 190 400
50 1225 2500
100 4950 10000
Notice: actual comparisons ≈ n²/2, which is still O(n²).
Sorting Strings and Real Objects — Bubble Sort Isn't Just for Numbers
Everything we've done so far sorted integers, but in the real world you'll sort names, products, grades — anything. Bubble Sort's comparison step is the only thing that changes. For strings, Java's compareTo() method does the heavy lifting: it returns a negative number if the first string comes before the second alphabetically, zero if they're equal, and a positive number if it comes after.
This is a great moment to understand what 'sorting' really means. The algorithm itself — the passes, the comparisons, the swaps — stays identical. Only the definition of 'which one is bigger' changes. This is why sorting algorithms are often taught with Comparators in production code: you separate the sorting logic from the comparison logic cleanly.
Sorting strings alphabetically is also a great way to cement your understanding because you can verify the output easily in your head. Try tracing through the passes yourself on paper before running the code — that's genuinely the fastest way to make this algorithm stick in your memory.
public class BubbleSortStrings { public static void main(String[] args) { // A list of student names that need to be sorted alphabetically String[] studentNames = {"Zara", "Ahmed", "Maya", "Liam", "Sofia", "Ben"}; System.out.println("Student names before sorting:"); printNames(studentNames); alphabeticalBubbleSort(studentNames); System.out.println("\nStudent names after sorting:"); printNames(studentNames); } static void alphabeticalBubbleSort(String[] names) { int size = names.length; for (int pass = 0; pass < size - 1; pass++) { boolean swappedThisPass = false; for (int index = 0; index < size - pass - 1; index++) { // compareTo() returns a positive number when names[index] // comes AFTER names[index+1] alphabetically. // That means they're in the wrong order — swap them. if (names[index].compareTo(names[index + 1]) > 0) { String temp = names[index]; names[index] = names[index + 1]; names[index + 1] = temp; swappedThisPass = true; } } if (!swappedThisPass) { break; // Early exit if already sorted } } } static void printNames(String[] names) { for (String name : names) { System.out.print(name + " "); } System.out.println(); } }
Zara Ahmed Maya Liam Sofia Ben
Student names after sorting:
Ahmed Ben Liam Maya Sofia Zara
| Aspect | Bubble Sort | Selection Sort |
|---|---|---|
| Best-case time | O(n) — with early exit flag | O(n²) — always scans full array |
| Worst-case time | O(n²) | O(n²) |
| Space complexity | O(1) — in-place | O(1) — in-place |
| Number of swaps | High — swaps at every out-of-order pair | Low — at most one swap per pass |
| Stable sort? | Yes — equal elements keep original order | No — can swap equal elements past each other |
| Detects sorted array? | Yes — with the swapped flag optimization | No — always runs all passes |
| Best real-world use | Nearly sorted small arrays | When minimising writes/swaps matters most |
🎯 Key Takeaways
- Bubble Sort repeatedly compares adjacent pairs and swaps them if out of order — the largest unsorted element 'bubbles' to its correct position at the end of each pass.
- Always include the 'swapped' early-exit flag. Without it, you have O(n²) best case. With it, you have O(n) best case — a critical difference on nearly-sorted data.
- Bubble Sort is O(n²) in the average and worst case, making it impractical for large datasets — but its O(1) space complexity and simplicity make it a perfect teaching algorithm and fine for tiny arrays.
- Bubble Sort is stable: equal elements never swap past each other, which means their original relative order is preserved — a property that matters when sorting objects by multiple fields.
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Forgetting to shrink the inner loop each pass — Symptom: the algorithm still works, but you're wastefully re-comparing elements that are already in their final sorted positions, making it slower than it needs to be. Fix: make the inner loop condition
index < size - pass - 1, notindex < size - 1. The- passis what shrinks the window each round. - ✕Mistake 2: Skipping the 'swapped' early-exit flag — Symptom: on an already-sorted or nearly-sorted array, the algorithm runs all n-1 passes anyway, showing your interviewer you haven't thought through the best case. Fix: add a boolean
swappedThisPass = falsebefore the inner loop, set it to true on any swap, and break out of the outer loop immediately if it's still false after a full pass. - ✕Mistake 3: Using the wrong comparison operator for descending order — Symptom: you change
>to<and expect it to sort largest-to-smallest, but you get confused when the logic feels backwards. Fix: think of it as 'if the left element is smaller than the right, they're in the wrong order for descending sort' — soarray[index] < array[index + 1]is correct for descending. Rename your variable to make the intent clear:boolean wantDescending = true;and comment the comparison direction.
Interview Questions on This Topic
- QWhat is the time complexity of Bubble Sort in the best, average, and worst case — and what input triggers each?
- QHow would you modify Bubble Sort to stop early if the array is already sorted, and why does that optimization matter?
- QIs Bubble Sort a stable sorting algorithm? What does 'stable' mean, and why does it matter when sorting objects by one field?
Frequently Asked Questions
Is bubble sort ever actually used in real software?
Rarely. Bubble Sort is primarily used as a teaching tool because its mechanics are easy to visualise. In production code you'd use language-built-in sorts like Java's Arrays.sort(), which uses a highly optimised Dual-Pivot Quicksort under the hood. The one exception: Bubble Sort with an early-exit flag is occasionally useful for tiny, nearly-sorted arrays where its simplicity and O(n) best case are valuable.
Why is it called Bubble Sort?
Because larger elements gradually 'bubble up' toward the end of the array over successive passes, just like air bubbles rise through water. After each pass, the largest remaining unsorted element has floated into its correct final position at the top of the unsorted portion.
What's the difference between a pass and a comparison in Bubble Sort?
A 'pass' is one full sweep of the inner loop from the start of the unsorted portion to its end. During each pass, you make multiple individual 'comparisons' — one for each neighboring pair you examine. An array of n elements requires up to n-1 passes, and each pass makes multiple comparisons, so the total comparison count grows quadratically.
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.