Skip to content
Tutorials Center
My learning

Topics

Lesson 80 of 225 · Sorting

Insertion Sort

Learn insertion sort in Python with a clear trace, shift counters, why it is fast on nearly sorted data, binary insertion, online sorting with bisect and O(n²) analysis.

Think about how you sort a hand of playing cards. You pick up one card at a time and slide it into the right place among the cards you are already holding. Your left hand always contains a sorted group, and each new card from the table is inserted into it. That is insertion sort.

Of the three simple sorts in this chapter, insertion sort is the one that real software actually uses. It is stable, in-place, and adaptive: if the data is nearly sorted it runs in almost linear time. That is why professional sorting routines, including Python's own Timsort, fall back to insertion sort for small pieces. In this lesson you will build it, trace it, measure how it reacts to different inputs, speed up the search with binary insertion, and see how it solves the problem of sorting data that arrives one item at a time.

The idea

Split the list into a sorted prefix and the rest. Take the first item of the rest (the "key"), and move it left past every larger item in the prefix until it fits.

TEXT
sort [7, 3, 9, 1, 5]

[7 | 3 9 1 5]     key = 3: 7 > 3, shift 7 right, insert 3
[3 7 | 9 1 5]     key = 9: 7 < 9, stays
[3 7 9 | 1 5]     key = 1: shift 9, 7, 3 right, insert 1 at the front
[1 3 7 9 | 5]     key = 5: shift 9, 7 right, 3 < 5 stop, insert 5
[1 3 5 7 9]

The invariant: before inserting item i, the first i items are the same items as in the original list's first i positions, but sorted. After the insertion that holds for i + 1.

Notice that we do not swap at every step. We shift larger items one place to the right (one write each), hold the key in a variable, and write it once in the gap that opens up.

The algorithm in plain words

  1. For i from 1 to n - 1:
  2. Save key = items[i] and set j = i - 1.
  3. While j >= 0 and items[j] > key: copy items[j] one place right (items[j + 1] = items[j]) and decrease j.
  4. Write the key into the gap: items[j + 1] = key.

The comparison is strictly greater (>), so an equal item is never jumped over. That makes insertion sort stable.

Implementation with counters

Python Insertion sort with comparisons and shifts

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For [7, 3, 9, 1, 5] the sort needs 8 comparisons and 6 shifts. The number of shifts is always exactly the number of inversions (pairs in the wrong order), and the number of comparisons is the number of shifts plus at most n - 1 (one extra comparison per item to discover where to stop). On the sorted list of eight, that is 7 comparisons and 0 shifts: a single linear scan.

Complexity

Case Comparisons Shifts Time
Best (sorted) n - 1 0 O(n)
Average (random) about n² / 4 about n² / 4 O(n²)
Worst (reversed) n(n - 1) / 2 n(n - 1) / 2 O(n²)

Space is O(1): one extra variable for the key. More precisely, the running time is O(n + d), where d is the number of inversions. If every item is at most k places from its final position, then d is at most n * k, so the time is O(n * k). That is the reason insertion sort shines on nearly sorted data.

Python Insertion sort loves nearly sorted input

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Selection sort pays 499,500 comparisons every time. Insertion sort pays about a thousand on sorted or nearly sorted input, about half of that (251,673) on shuffled input, and the full amount only on reversed input. When you know your data is "almost in order", such as a log file that is mostly in time order, insertion sort is a great choice.

Faster search: binary insertion sort

In step 3 we scan left through a sorted prefix to find the insertion point. A sorted prefix is exactly what binary search likes: we can find the position with O(log i) comparisons instead of up to i.

Python Binary insertion sort and counting comparisons

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Binary insertion sort needs far fewer comparisons (O(n log n) in total; 3,989 instead of 124,750 for 500 items), which helps when comparing is expensive, such as comparing long strings. But the shifts are still there, since making room in an array means moving items. Total time stays O(n²). In Python, list.insert(index, value) does the shifting for you in fast C code.

Online sorting: keep a list sorted as items arrive

Insertion sort is online: it can sort a stream, taking each new item and inserting it into the already-sorted part, without needing to see all the data first. Python's bisect.insort does exactly one binary insertion step.

Python Online sorting with bisect.insort

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each insort costs O(log n) to find the spot and O(n) to shift, but at the moment of arrival the data is always sorted and ready to query. If you need the minimum of a stream, a priority queue is cheaper.

Where insertion sort is used for real

  • Timsort (Python, Java's object sort) sorts tiny runs with binary insertion sort and then merges them.
  • Quick sort and introsort implementations switch to insertion sort when a piece gets small (often under 16 or so items), because for tiny inputs its simplicity beats the overhead of recursion.
  • Shell sort is insertion sort run on items that are far apart first (see Shell sort and Timsort).

When you meet a problem that says "the array is almost sorted" or "each element is at most k positions away from its sorted position", think insertion sort (O(n * k)) or a small heap of size k+1 (O(n log k)).

Common mistakes

  • Using >= in the while loop. The sort still works but loses stability and moves equal items needlessly.
  • Writing items[j] = key instead of items[j + 1] = key after the loop.
  • Checking items[j] > key before j >= 0, which reads items[-1] (the last item) in Python and gives wrong answers instead of an error. Always test the index bound first.
  • Swapping neighbours at every step. It works but writes three times as much as shifting.
  • Forgetting that Python's negative indexes never raise errors, so an off-by-one at the left edge is silent.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What is the best-case time complexity of insertion sort and when does it happen?

    On sorted input every key is compared once with its left neighbour and stays, so the algorithm makes n - 1 comparisons and no shifts.
  2. 2. How many shifts does insertion sort make on [3, 1, 2]?

    The pairs (3, 1) and (3, 2) are out of order, so there are 2 inversions. Each shift removes exactly one inversion, so exactly 2 shifts are made.
  3. 3. Which sorted-prefix search does binary insertion sort use to find the insertion point?

    The prefix is sorted, so binary search finds the insertion point in O(log i) comparisons. Shifting the items still costs O(i), so the total time stays O(n²).
  4. 4. Why is insertion sort called an online algorithm?

    At every moment the prefix processed so far is sorted, so a new item can simply be inserted into it.
  5. 5. In a Python implementation, what goes wrong if the loop condition is items[j] > key and j >= 0?

    Python allows negative indexes, so items[-1] is the last element. The bound test j >= 0 must come first so that the second condition is never evaluated with j = -1.

Summary

  • Insertion sort grows a sorted prefix by inserting each next item at the right spot, shifting larger items right.
  • Time is O(n + d) where d is the number of inversions: O(n) on sorted input, O(n²) on average and in the worst case; space is O(1).
  • It is stable, in-place, adaptive and online.
  • Binary insertion sort cuts the comparisons to O(n log n), but the shifting keeps the total at O(n²).
  • Real libraries use it for small pieces inside faster algorithms such as Timsort.
  • bisect.insort keeps a list sorted as items arrive.

Next: Merge Sort