Bubble Sort — The Simplest Sort

26 Jan 2026

Introduction

Imagine you are a teacher lining up students by height for a class photo. You start at one end and compare each pair of neighbouring students. If the taller student is standing before the shorter one, you ask them to swap places. You keep walking back and forth along the line until nobody needs to swap anymore.

That is Bubble Sort in a nutshell. It gets its name because, with each pass through the array, the largest unsorted element “bubbles up” to its correct position at the end — just like air bubbles rising to the surface of water.

It is not the most efficient sort (we will see better ones very soon), but it is the easiest to understand and a perfect starting point for learning how sorting algorithms work.

How Bubble Sort Works

The algorithm follows a simple loop:

Walk through the array from left to right.
Compare each pair of adjacent elements.
If the left element is greater than the right element, swap them.
After one complete pass, the largest element is guaranteed to be at the end.
Repeat for the remaining unsorted portion, ignoring the already-sorted tail.
Stop when a complete pass has no swaps — the array is sorted.

Step-by-Step Walkthrough

Let’s sort the array [29, 10, 14, 37, 13] using Bubble Sort.

Pass 1

Compare	Array State	Action
29 vs 10	`[29, 10, 14, 37, 13]`	29 > 10 → swap
29 vs 14	`[10, 29, 14, 37, 13]`	29 > 14 → swap
29 vs 37	`[10, 14, 29, 37, 13]`	29 < 37 → no swap
37 vs 13	`[10, 14, 29, 37, 13]`	37 > 13 → swap

After Pass 1: [10, 14, 29, 13, 37] — 37 has bubbled to its correct position. ✅

Pass 2

Compare	Array State	Action
10 vs 14	`[10, 14, 29, 13, 37]`	10 < 14 → no swap
14 vs 29	`[10, 14, 29, 13, 37]`	14 < 29 → no swap
29 vs 13	`[10, 14, 29, 13, 37]`	29 > 13 → swap

After Pass 2: [10, 14, 13, 29, 37] — 29 is in place. ✅

Pass 3

Compare	Array State	Action
10 vs 14	`[10, 14, 13, 29, 37]`	10 < 14 → no swap
14 vs 13	`[10, 14, 13, 29, 37]`	14 > 13 → swap

After Pass 3: [10, 13, 14, 29, 37] — 14 is in place. ✅

Pass 4

Compare	Array State	Action
10 vs 13	`[10, 13, 14, 29, 37]`	10 < 13 → no swap

No swaps occurred! The algorithm detects this and stops early.

Final sorted array: [10, 13, 14, 29, 37] ✅

Java Implementation

public class BubbleSort {

    /**
     * Sorts an integer array in ascending order using Bubble Sort.
     *
     * Optimisation: if no swaps occur during a pass, the array is
     * already sorted and we can stop early.
     */
    public static void bubbleSort(int[] arr) {
        int n = arr.length;

        // Outer loop: each pass places the next-largest element at the end
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false; // track if any swap happened this pass

            // Inner loop: compare adjacent pairs
            // (n - 1 - i) because the last i elements are already in place
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap the two elements
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            // If no swaps happened, the array is already sorted — stop early
            if (!swapped) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers = {29, 10, 14, 37, 13};

        System.out.println("Before sorting:");
        printArray(numbers);

        bubbleSort(numbers);

        System.out.println("After sorting:");
        printArray(numbers);
    }

    private static void printArray(int[] arr) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if (i < arr.length - 1) sb.append(", ");
        }
        sb.append("]");
        System.out.println(sb);
    }
}

Output:

Before sorting:
[29, 10, 14, 37, 13]
After sorting:
[10, 13, 14, 29, 37]

Key Lines Explained

Line	Purpose
`for (int i = 0; i < n - 1; i++)`	Each pass guarantees one more element is in its final position. After i passes, the last i elements are sorted.
`for (int j = 0; j < n - 1 - i; j++)`	We only need to compare elements in the unsorted portion. The `- i` shrinks the window each pass.
`boolean swapped = false;`	Our early-exit optimisation flag. If we go through an entire pass with zero swaps, the array must already be sorted.
`if (!swapped) break;`	This is what turns the worst case from always $O(n^2)$ into a best case of $O(n)$.

Time & Space Complexity Analysis

Case	Time Complexity	Explanation
Best	$O(n)$	Array is already sorted. One pass with zero swaps → early exit.
Average	$O(n^2)$	Elements are in random order. Roughly $\frac{n(n-1)}{2}$ comparisons.
Worst	$O(n^2)$	Array is in reverse order. Every pair needs swapping on every pass.

| Space Complexity | $O(1)$ | |:-:|:-:|

Bubble Sort is an in-place algorithm — it only uses a constant amount of extra memory (the temp variable and the swapped flag), regardless of input size. It is also stable, meaning equal elements maintain their original relative order.

When to Use / When NOT to Use

✅ Use When	❌ Avoid When
Teaching or learning sorting fundamentals	Production code with medium to large datasets
The array is very small (< 20 elements)	Performance matters — $O(n^2)$ is too slow for thousands of elements
The array is nearly sorted (the early-exit optimisation shines here)	You need a guaranteed $O(n \log n)$ sort — use Merge Sort instead

Practice Problems

Sort an Array – LeetCode #912 — Implement Bubble Sort first, then try to beat the time limit with a faster algorithm.
Sorting: Bubble Sort – HackerRank — Count the number of swaps and print the results.
Challenge: Modify the algorithm to sort in descending order. What line do you change?

What’s Next?

Bubble Sort showed us the concept of comparison-based sorting. Next, we will look at two more $O(n^2)$ algorithms that each have their own clever twist: Selection Sort & Insertion Sort.