Skip to content

Volume ITechnology

4.0.24 — Bubble Sort ​

Classic · Easy · taught first in every course, asked as "sort without sort()"

The problem ​

Sort a list of numbers in increasing order, without using sort() or sorted().

[5, 1, 4, 2, 8]  →  [1, 2, 4, 5, 8]

The next seven pages each solve this one problem a different way. Each way teaches something different about how sorting can work, and each comes up in interviews. Chapter 4.10 compares them all side by side once you have seen them.

Two words used on every sorting page ​

A sort is in place if it rearranges the list using only a fixed, small amount of extra memory, no matter how long the list is. It does not build a second list.

A sort is stable if equal values stay in the order they started in. Sorting numbers, you cannot tell. But suppose you sort exam papers by mark, and two students both scored 72. A stable sort keeps them in the order they were handed in. This matters when you sort by one thing and then another. Sort by name, then stably by mark, and students with the same mark stay in name order.

The idea ​

Walk along the list, looking at each pair of neighbours. If a pair is in the wrong order, swap it. After one full walk, the largest value has been carried all the way to the end.

Why? When the walk reaches the largest value, it is bigger than its right neighbour, so it is swapped one step right. Now it is still the bigger of the next pair, so it moves again. It keeps moving right until it reaches the end. Like a bubble rising in water, which is where the name comes from. The name was in print by 1962.

Repeat the walk. Each walk pushes the largest remaining value to its final place, just before the ones already finished. After n - 1 walks, everything is in place.

The solution ​

python
def bubble_sort(nums: list[int]) -> None:
    n = len(nums)
    for i in range(n - 1):                    # (1)
        swapped = False
        for j in range(n - 1 - i):            # (2)
            if nums[j] > nums[j + 1]:         # (3)
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                swapped = True
        if not swapped:                       # (4)
            break

a = [5, 1, 4, 2, 8]
bubble_sort(a)
print(a)   # → [1, 2, 4, 5, 8]

b = [3, 3, 1]
bubble_sort(b)
print(b)   # → [1, 3, 3]

(1) At most n - 1 walks. After n - 1 values are in their final places, the last one has nowhere else to be.

(2) After walk number i (counting from 0), the last i positions are already finished. So each walk can stop i places earlier. n - 1 - i is the number of pairs still worth checking. Without the - i, the code is still correct, but it keeps rechecking the finished part for no reason.

(3) Swap only when the left value is strictly bigger. Equal neighbours are never swapped. That is what makes bubble sort stable. Using >= would swap equal values, and the sort would no longer be stable.

(4) If a whole walk made no swaps, every neighbour pair is already in order. That means the whole list is sorted. Stop early.

Trace ​

On [5, 1, 4, 2, 8]. Each row is one swap or no-swap decision in the first walk.

pair comparedswap?list after
5, 1yes1 5 4 2 8
5, 4yes1 4 5 2 8
5, 2yes1 4 2 5 8
5, 8no1 4 2 5 8

After walk 1, the 8 is in place. (It was already the largest and already at the end.) Walk 2 swaps 4 and 2, giving 1 2 4 5 8. Walk 3 makes no swaps, so the early exit stops the sort.

Complexity, worked out ​

Comparisons in the worst case. Walk 1 checks n - 1 pairs, walk 2 checks n - 2, and so on down to 1.

(n - 1) + (n - 2) + \dots + 1 = \frac{n(n-1)}{2}

This is the same "add 1 to n" sum from 4.0.16, stopping at n - 1. For 1,000 elements that is 499,500 comparisons. It grows like n^2, so it is O(n^2).

Swaps in the worst case. Each swap fixes exactly one inversion. An inversion is a pair of values that are in the wrong order relative to each other. For example, in [3, 1, 2], the pairs (3, 1) and (3, 2) are inversions. Swapping two neighbours that are out of order fixes exactly that one pair, and changes no other pair's order. So bubble sort does exactly as many swaps as the list has inversions. A list in reverse order has every pair inverted, \frac{n(n-1)}{2} of them. That is the most work possible.

The best case. On a list that is already sorted, the first walk makes n - 1 comparisons and no swaps. The early exit stops it. That is O(n). Without the swapped flag, it would still do all \frac{n(n-1)}{2} comparisons.

Average case. A random list has about half of all pairs inverted, so about \frac{n(n-1)}{4} swaps. Still O(n^2).

Memory. Only i, j and swapped. O(1) extra memory, so it is in place.

CaseTime
Best (already sorted)O(n)
AverageO(n^2)
Worst (reversed)O(n^2)
Extra memoryO(1)
StableYes

Should you ever use it? ​

No. Insertion sort (4.0.26) has the same O(n^2) worst case, but does fewer writes and is faster in practice. Bubble sort survives because it is the easiest sort to explain and to prove correct. Donald Knuth, in his famous series The Art of Computer Programming, wrote that bubble sort seems to have nothing to recommend it except a catchy name. In 2007, at Google, Barack Obama was asked how to sort a million numbers. He joked that "the bubble sort would be the wrong way to go". The audience laughed, because it is true.

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"What is the best case of bubble sort?"O(n), when the list is already sorted. But only if the code stops when a whole pass makes no swaps. Without that check, it still does O(n^2) work.

"Is bubble sort stable?" Yes. It swaps only when the left value is strictly bigger. Using >= would swap equal values and make it unstable.

"Why can the inner loop stop at n - 1 - i?" Each pass moves one more large value to its final place at the end. Those last i places do not need checking again.

"How many swaps does bubble sort make?" Exactly the number of pairs that are in the wrong order. A reversed list has the most such pairs.

One thing to volunteer: "No sort that only swaps neighbours can beat O(n^2) on average. That is why merge sort and quicksort move values over long distances."

Next: 4.0.25 Selection Sort. Find the smallest, put it first, repeat. The sort with the fewest swaps.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet