Bubble Sort Complete Guide

Algorithm • medium

Bubble sort repeatedly compares adjacent elements and swaps out-of-order pairs until the list is sorted.

It is mainly valuable as a teaching algorithm because its mechanics are intuitive and visual.

At scale, bubble sort is usually replaced by faster O(n log n) algorithms.

Typical Complexity Baseline

Metric	Value
Complexity Note 1	Average/Worst `O(n^2)`
Best	`O(n)` with early-exit optimization

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Bubble sort adjacent swaps

Each pass walks the array and swaps neighbors that are out of order.

Step 1/22Start with [5, 3, 8, 1, 6, 2]. Walk left→right comparing adjacent pairs; the biggest values bubble to the right.

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Bubble sort in 2 minutes

Channel: Michael Sambol

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Outer pass

What it is Each pass bubbles the largest remaining element to the end.

Why it matters Outer pass is a required building block for understanding how Bubble Sort stays correct and performant on large inputs.

Adjacent comparison

What it is Compare index i and i+1, then swap if needed.

Why it matters Adjacent comparison is a required building block for understanding how Bubble Sort stays correct and performant on large inputs.

Swap operation

What it is In-place exchange of adjacent values.

Why it matters Swap operation is a required building block for understanding how Bubble Sort stays correct and performant on large inputs.

Early-exit flag

What it is Stop when a full pass makes zero swaps.

Why it matters Early-exit flag is a required building block for understanding how Bubble Sort stays correct and performant on large inputs.

Shrinking boundary

What it is Ignore already sorted tail section in later passes.

Why it matters Shrinking boundary is a required building block for understanding how Bubble Sort stays correct and performant on large inputs.

Adjacent swap

What it is Swap two neighboring values only.

Why it matters Swap two neighboring values only. In Bubble Sort, this definition helps you reason about correctness and complexity when inputs scale.

Stable sort

What it is Equal values preserve relative order.

Why it matters Equal values preserve relative order. In Bubble Sort, this definition helps you reason about correctness and complexity when inputs scale.

Best case

What it is With early-exit, sorted input can finish in O(n).

Why it matters With early-exit, sorted input can finish in O(n). In Bubble Sort, this definition helps you reason about correctness and complexity when inputs scale.

Worst case

What it is Reverse-sorted input needs O(n^2) comparisons/swaps.

Why it matters Reverse-sorted input needs O(n^2) comparisons/swaps. In Bubble Sort, this definition helps you reason about correctness and complexity when inputs scale.

In-place

What it is Uses constant extra memory beyond input array.

Why it matters Uses constant extra memory beyond input array. In Bubble Sort, this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/22

Start with [5, 3, 8, 1, 6, 2]. Walk left→right comparing adjacent pairs; the biggest values bubble to the right.

Step 2/22

Pass 1 · arr[0]=5 > arr[1]=3 → swap. Array now [3, 5, 8, 1, 6, 2].

Step 3/22

Pass 1 · arr[1]=5 ≤ arr[2]=8 → no swap.

Step 4/22

Pass 1 · arr[2]=8 > arr[3]=1 → swap. Array now [3, 5, 1, 8, 6, 2].

Step 5/22

Pass 1 · arr[3]=8 > arr[4]=6 → swap. Array now [3, 5, 1, 6, 8, 2].

Step 6/22

Pass 1 · arr[4]=8 > arr[5]=2 → swap. Array now [3, 5, 1, 6, 2, 8].

Step 7/22

Pass 1 done. arr[5]=8 is now locked.

Step 8/22

Pass 2 · arr[0]=3 ≤ arr[1]=5 → no swap.

Step 9/22

Pass 2 · arr[1]=5 > arr[2]=1 → swap. Array now [3, 1, 5, 6, 2, 8].

Step 10/22

Pass 2 · arr[2]=5 ≤ arr[3]=6 → no swap.

Step 11/22

Pass 2 · arr[3]=6 > arr[4]=2 → swap. Array now [3, 1, 5, 2, 6, 8].

Step 12/22

Pass 2 done. arr[4]=6 is now locked.

Step 13/22

Pass 3 · arr[0]=3 > arr[1]=1 → swap. Array now [1, 3, 5, 2, 6, 8].

Step 14/22

Pass 3 · arr[1]=3 ≤ arr[2]=5 → no swap.

Step 15/22

Pass 3 · arr[2]=5 > arr[3]=2 → swap. Array now [1, 3, 2, 5, 6, 8].

Step 16/22

Pass 3 done. arr[3]=5 is now locked.

Step 17/22

Pass 4 · arr[0]=1 ≤ arr[1]=3 → no swap.

Step 18/22

Pass 4 · arr[1]=3 > arr[2]=2 → swap. Array now [1, 2, 3, 5, 6, 8].

Step 19/22

Pass 4 done. arr[2]=3 is now locked.

Step 20/22

Pass 5 · arr[0]=1 ≤ arr[1]=2 → no swap.

Step 21/22

Pass 5 done. arr[1]=2 is now locked.

Step 22/22

Sorted! Worst case O(n²) comparisons.

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Merge Sort

Choose this when Choose bubble sort only for learning or tiny datasets.

Tradeoff Merge sort is much faster for non-trivial input sizes.

vs. Quick Sort

Choose this when Bubble is simpler to explain line-by-line.

Tradeoff Quick sort is far better in practical runtime.

vs. Insertion Sort

Choose this when Bubble may be easier to visualize in classrooms.

Tradeoff Insertion sort usually performs fewer writes on near-sorted data.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

CS education platforms

Learning environments use bubble sort visualizations to teach comparisons and swaps before advanced algorithms.

Takeaway Bubble sort is a strong pedagogy tool, not a production workhorse.

Embedded prototypes

Tiny fixed-size arrays in constrained firmware sometimes use simple O(n^2) routines for readability.

Takeaway For very small n, code simplicity can outweigh asymptotic optimality.

Interview prep companies

Candidate training often starts with bubble sort to build intuition for loop invariants and boundary handling.

Takeaway Foundational understanding improves mastery of faster sorts later.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Stop once a pass makes no swaps, indicating the list is already sorted.

Complexity: Average/Worst O(n^2), Best O(n), Space O(1)

Bubble sort with early-exit optimization

Language

function bubbleSort(values: number[]): number[] {
  const sortedValues = [...values]
  for (let passIndex = 0; passIndex < sortedValues.length - 1; passIndex += 1) {
    let didSwap = false
    for (let compareIndex = 0; compareIndex < sortedValues.length - 1 - passIndex; compareIndex += 1) {
      if (sortedValues[compareIndex] > sortedValues[compareIndex + 1]) {
        ;[sortedValues[compareIndex], sortedValues[compareIndex + 1]] = [sortedValues[compareIndex + 1], sortedValues[compareIndex]]
        didSwap = true
      }
    }
    if (!didSwap) break
  }
  return sortedValues
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

Running full n passes even when array is already sorted.
Ignoring shrinking upper bound and doing redundant comparisons.
Using bubble sort on large production datasets.
Off-by-one errors in inner loop boundary.
Assuming O(n) behavior without early-exit optimization.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

Bubble sort is mainly for learning and tiny inputs, not production-scale datasets.
Use early-exit flag so already-sorted data finishes in linear time.
Shrink the inner loop boundary each pass because the tail becomes sorted.
Step through a five-element example manually to internalize swap flow.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

Great for learning sorting fundamentals and swap-based ordering.
Very easy to implement and debug step-by-step.
Can short-circuit early when input is already sorted.

LeetCode-specific tips (pattern-identification signals)

Identification signal: educational adjacent-swap process is required explicitly or for teaching mechanics.
Identification signal: problem expects simple in-place sort with tiny inputs where clarity matters more than scale.
If prompt emphasizes repeated neighbor comparisons/swaps, bubble sort pattern is being tested.
For Bubble Sort questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Valid Anagram	Easy	`O(n log n)` with sorting
2	Merge Sorted Array	Easy	`O(n+m)`
3	Height Checker	Easy	`O(n log n)`
4	Sort an Array	Medium	`O(n^2)` for bubble approach
5	Sort Colors	Medium	`O(n)` optimal, `O(n^2)` naive bubble
6	Largest Number	Medium	`O(n log n)`
7	Wiggle Sort II	Medium	`O(n log n)`
8	Sort List	Medium	`O(n log n)`
9	Count of Smaller Numbers After Self	Hard	`O(n log n)`
10	Reverse Pairs	Hard	`O(n log n)`