Skip to content

Volume ITechnology

4.0.26 — Insertion Sort ​

Classic · Easy · LeetCode 147 (Insertion Sort List) · the simple sort real libraries still use

The problem ​

Sort a list in increasing order without sort().

[12, 11, 13, 5, 6]  →  [5, 6, 11, 12, 13]

The idea ​

This is how most people sort cards as they are dealt. You hold a sorted hand. A new card arrives. You slide it left past every card bigger than it, and drop it into the gap. Your hand is sorted again.

In a list, the left part is the sorted hand. It starts as just the first element, since one element is always sorted. Each step takes the next element and inserts it into the right place in the sorted part. The sorted part grows by one.

The solution ​

python
def insertion_sort(nums: list[int]) -> None:
    for i in range(1, len(nums)):          # (1)
        value = nums[i]                    # (2)
        j = i - 1
        while j >= 0 and nums[j] > value:  # (3)
            nums[j + 1] = nums[j]          # (4)
            j -= 1
        nums[j + 1] = value                # (5)

a = [12, 11, 13, 5, 6]
insertion_sort(a)
print(a)   # → [5, 6, 11, 12, 13]

(1) nums[:i] is already sorted. Start at i = 1, because a single element is sorted by itself.

(2) Lift the new element out and hold it in value. Its slot is now free to be overwritten.

(3) Walk left through the sorted part while the values there are bigger than value. Check j >= 0 first. If j became -1 and we read nums[-1], Python would quietly give us the last element of the list, not an error. The loop would then compare against the wrong value. Putting j >= 0 first stops before that read happens.

(4) Shift the bigger value one step right. This is not a swap. A swap writes two values. A shift writes one. Moving value along with a chain of swaps would cost three times as many writes.

(5) j stopped at a value that is not bigger than value, or at -1. The gap is just to its right. Drop value in.

Stability. Line (3) uses >, so the walk stops at an equal value. The new element lands to the right of it. Equal values keep their original order, so insertion sort is stable. With >=, it would walk past equal values and lose that.

Trace ​

On [12, 11, 13, 5, 6]. The bar | separates the sorted part from the rest.

stepvaluewhat happenslist after
start12 | 11 13 5 6
i=11112 shifts right, 11 drops in at 011 12 | 13 5 6
i=21312 is not bigger, nothing moves11 12 13 | 5 6
i=3513, 12, 11 shift right, 5 drops in at 05 11 12 13 | 6
i=4613, 12, 11 shift right, stops at 55 6 11 12 13

Complexity, worked out ​

The cost is the number of shifts, plus one comparison per element to stop.

Worst case: reversed input. Each new value is smaller than everything before it, so it walks all the way to the front. Element i shifts i values. In total:

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

That is O(n^2).

Best case: already sorted. Each new value is already bigger than the last sorted value. The while check fails at once. One comparison per element. That is O(n).

The case that matters most: nearly sorted. Say every element is at most k places from where it belongs. Then each element shifts at most k times. The total is at most n \times k, so O(nk). For a list that is sorted except for a few late arrivals, that is close to O(n).

The exact rule: the number of shifts equals the number of inversions, the out-of-order pairs from 4.0.24. Every shift moves one bigger value past value, which fixes exactly one inversion. So insertion sort does as much work as the list is unsorted, and no more. Selection sort, in contrast, does \frac{n(n-1)}{2} comparisons whatever the input is.

Memory. Only value, i and j. O(1) extra. It is in place.

CaseTime
Best (sorted)O(n)
Nearly sorted, each element within kO(nk)
AverageO(n^2)
Worst (reversed)O(n^2)
Extra memoryO(1)
StableYes

Why it is the one simple sort still in use ​

It is fast on small lists. For a list of about 10 to 30 elements, insertion sort beats merge sort and quicksort. It has no recursion, no extra memory and a very tight loop. Big-O hides constant costs, and for small n the constants win. So real sorting libraries use insertion sort for small pieces. Python's built-in sort, Timsort, written by Tim Peters in 2002, uses insertion sort to build small sorted runs before merging them. C++'s std::sort switches to insertion sort below about 16 elements.

It is fast on nearly-sorted data. Real data is often almost in order. A leaderboard that changes a little each minute is one example. A log of events that arrive slightly out of time order is another.

It can sort as data arrives. It never needs to see the whole list first. Each new element is inserted into what is already sorted. A sort with this property is called online.

A variation: binary insertion sort ​

The sorted part is sorted, so you can find where value belongs with binary search, in O(\log i) comparisons instead of O(i). Binary search is covered in 4.11.1. Python's bisect module does it.

python
import bisect

def binary_insertion_sort(nums: list[int]) -> list[int]:
    out = []
    for x in nums:
        bisect.insort_right(out, x)    # (1)
    return out

print(binary_insertion_sort([12, 11, 13, 5, 6]))   # → [5, 6, 11, 12, 13]

(1) insort_right finds the place with binary search, after any equal values, which keeps the sort stable. Then it inserts there.

But the shifts do not go away. Inserting into the middle of a list still moves every later element one place. So it is still O(n^2) in the worst case. It only helps when comparisons are much more expensive than moves, such as comparing long strings.

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 are the best and worst cases?" Best case O(n), on a sorted list. Worst case O(n^2), on a reversed list. The work grows with how many pairs are out of order.

"Why shift instead of swap?" A shift writes one value. A swap writes two. Shifting does less work.

"Why does the loop check j >= 0 first?" In Python, nums[-1] does not crash. It quietly gives the last element. Checking j >= 0 first stops that wrong read.

"Where is insertion sort used in real life?" Inside Python's built-in sort and C++'s std::sort, for small pieces of the list, and for lists that are almost sorted.

"Does binary search make it O(n \log n)?" No. It finds the right place faster, but moving the other values to make room is still O(n^2) in total.

One thing to volunteer: "Insertion sort does less work the more sorted the list already is. That is why real libraries still use it."

Next: 4.0.27 Merge Sort. Split in half, sort each half, merge. The first sort that is O(n \log n) every time.

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