Python Tutorial
Insertion Sort
Build a sorted list one element at a time by inserting each new value into its correct place.
How Insertion Sort Works
Insertion sort works the way you sort playing cards in your hand. Starting from the second element, take each value ("the key") and shift larger elements to its left one step right, then drop the key into the gap. The left part stays sorted at every step.
It is O(n²) in the worst case but O(n) on nearly-sorted data, stable, in-place, and fast for small inputs — which is why Timsort uses it for small runs.
Implementation
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift larger element right
j -= 1
arr[j + 1] = key # drop key into place
return arr
print(insertion_sort([12, 11, 13, 5, 6]))
# [5, 6, 11, 12, 13]Step-by-Step
Sorting [12, 11, 13, 5, 6]:
| Key | Array after insertion |
|---|---|
| 11 | [11, 12, 13, 5, 6] |
| 13 | [11, 12, 13, 5, 6] |
| 5 | [5, 11, 12, 13, 6] |
| 6 | [5, 6, 11, 12, 13] |
Complexity
| Case | Time |
|---|---|
| Best (already sorted) | O(n) |
| Average | O(n²) |
| Worst (reverse sorted) | O(n²) |
| Space | O(1) in place |
Insertion sort is stable and adaptive — its running time shrinks toward O(n) as the input becomes more sorted.
Where It Shines
- Small arrays (roughly n < 20), where its low overhead beats fancier sorts.
- Nearly-sorted data, or data arriving one item at a time (online sorting).
- As the base case inside hybrid sorts like Timsort and introsort.
Python's built-in Timsort splits data into small runs and sorts each with insertion sort, then merges them — combining insertion sort's speed on small/sorted data with merge sort's O(n log n) guarantee.
Best Practices
- Choose insertion sort for small or nearly-sorted inputs.
- Prefer it over bubble and selection sort as the simple sort to keep in your toolkit.
- For anything large or general-purpose, use
sorted()/list.sort().
Try It Yourself
Exercise 1: On already-sorted data, what is insertion sort's time complexity?
Show solution
O(n) — each element is already in place, so the inner loop never shifts.
Exercise 2: Why is insertion sort used inside hybrid sorts like Timsort?
Show solution
It is very fast on small or nearly-sorted runs and is stable, making it ideal for sorting the small chunks that Timsort then merges.
📘 Real-World Deep Dive
Knowing <strong>DSA Insertion Sort (algorithms & data structures)</strong> well is what turns algorithms & data structures from a curiosity into a daily tool — you'll reach for it in nearly every real project.
Real-Life Scenario
An end-to-end usage of DSA Insertion Sort that you'd actually see in a data pipeline or analytics notebook.
Real-Life Example
def insertion(xs):
for i in range(1, len(xs)):
cur = xs[i]; j = i - 1
while j >= 0 and xs[j] > cur:
xs[j+1] = xs[j]; j -= 1
xs[j+1] = cur
return xs
print(insertion([12, 11, 13, 5, 6]))Expected Output
(see source)Common mistakes
- Off-by-one errors in binary-search: the standard idiom is
while lo <= hiwithmid = (lo + hi) // 2. - Recursive algorithms blow the stack for n > ~10⁴; convert to iterative with an explicit stack.
- Comparison algorithms (
sorted(iterable)) are stable by default in Python — surprising for Java/C++ users. - Treating DSA Insertion Sort as a black box without reading the docs — the API has subtle defaults that bite when you scale.
🚀 Performance & Best Practices
- Use
bisect.bisect_left/bisect_rightinstead of writing your own binary search. - Convert a sorted search into a tuple-access pattern with
numpy.searchsortedfor huge arrays. - Use
heapqfor priority queues instead of maintaining a sorted list manually. - When working with algorithms & data structures, prefer vectorised / batched operations over Python loops.
🧪 Try It Yourself
- Reproduce the snippet on a representative slice of your own data.
- Profile the snippet with
cProfileortimeitand find the single biggest improvement. - Generalise the snippet into a small, reusable function you can drop into future projects.