Sorting and SearchingLesson 2

Insertion Sort

Build a sorted section one element at a time — like sorting a hand of cards. Simple, stable, and great for nearly-sorted data.

What Is It?

Insertion Sort works exactly like sorting playing cards in your hand. Take one card at a time from the pile. Insert it into the correct spot in your already-sorted hand, shifting other cards over to make room. Repeat until the pile is empty.

In code: the algorithm keeps a sorted portion at the beginning of the array. It takes the next unsorted element, finds its correct position in the sorted portion, and shifts everything larger one spot to the right to make room.

Analogy

You pick up cards one at a time from a face-down pile. Each time you pick up a new card, you slide it into the right position among the cards already in your hand. If your hand has [2, 4, 7, 9] and you pick up a 5, you slide the 7 and 9 right and insert the 5 between the 4 and 7. Your hand is always sorted.

Most people sort cards this way naturally. Insertion Sort is the algorithmic version of this intuition.

How It Works

The Algorithm

  1. Start with the first element — a single element is already sorted.
  2. Take the next element (call it the "key").
  3. Compare the key against elements in the sorted portion, moving right to left.
  4. Shift each element that is larger than the key one position to the right.
  5. Put the key in the gap that was created.
  6. Repeat for every remaining element.

Pseudocode

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
function insertionSort(arr):
    n = length(arr)
​
    for i from 1 to n - 1:            // start from index 1
        key = arr[i]                   // element to place
        j = i - 1                      // look left from here
​
        // shift elements larger than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]        // shift right
            j = j - 1
​
        arr[j + 1] = key               // place key in the gap

Step-by-Step Trace on [5, 3, 8, 1, 2]

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Initial: [5, 3, 8, 1, 2]
​
--- i=1: key=3, sorted part={5} ---
  5 > 3? Yes. Shift 5 right: [5, 5, 8, 1, 2]
  Place 3 at position 0:     [3, 5, 8, 1, 2]
  Sorted: {3, 5}
​
--- i=2: key=8, sorted part={3, 5} ---
  5 > 8? No. Stop.
  8 is already in the right place: [3, 5, 8, 1, 2]
  Sorted: {3, 5, 8}
​
--- i=3: key=1, sorted part={3, 5, 8} ---
  8 > 1? Yes. Shift: [3, 5, 8, 8, 2]
  5 > 1? Yes. Shift: [3, 5, 5, 8, 2]
  3 > 1? Yes. Shift: [3, 3, 5, 8, 2]
  Place 1 at position 0: [1, 3, 5, 8, 2]
  Sorted: {1, 3, 5, 8}
​
--- i=4: key=2, sorted part={1, 3, 5, 8} ---
  8 > 2? Yes. Shift: [1, 3, 5, 8, 8]
  5 > 2? Yes. Shift: [1, 3, 5, 5, 8]
  3 > 2? Yes. Shift: [1, 3, 3, 5, 8]
  1 > 2? No. Stop.
  Place 2 at position 1: [1, 2, 3, 5, 8]
  Sorted: {1, 2, 3, 5, 8}
​
Final: [1, 2, 3, 5, 8]

Sorted Portion Growing

Sorted Portion Growth— The sorted region (highlighted) grows by one element each step
1 / 5
Step 0: sorted={5}
5
3
8
1
2
[0]
[1]
[2]
[3]
[4]

Time Complexity

Worst case: O(n²) — array is reverse sorted. Every element must shift all the way to the front.

Worst Case: Reverse Sorted— Every element must travel all the way to the front — O(n^2) shifts
1 / 5
Initial (reverse sorted)
5
4
3
2
1
[0]
[1]
[2]
[3]
[4]

Best case: O(n) — array is already sorted. The inner while loop never runs because no element is out of place.

Best Case: Already Sorted— No shifts needed — each element is already in place — O(n)
1 / 5
Initial (already sorted)
1
2
3
4
5
[0]
[1]
[2]
[3]
[4]

Average case: O(n²) — on average, each element shifts about halfway through the sorted portion.

Space: O(1) — sorts in place, only the key variable is extra.

Stable: Yes — equal elements keep their original order because we only shift elements that are strictly greater than the key.

Why Insertion Sort Is Special

Insertion Sort is the best simple sorting algorithm for nearly sorted data. If each element is only a few positions away from where it belongs, Insertion Sort is extremely fast — much faster than O(n²) in practice.

This is why many real-world sorting implementations use Insertion Sort for small arrays (fewer than about 20 elements). The overhead of fancier algorithms is not worth it at small sizes.

Comparison of All Three Simple Sorts

Bubble Sort

  • Worst/avg: O(n²), Best: O(n)
  • Space: O(1) | Stable: Yes
  • Adaptive: Yes (early exit)

swap adjacent pairs

Selection Sort

  • All cases: O(n²)
  • Space: O(1) | Stable: No
  • Minimizes swaps: O(n)

select min each pass

Insertion Sort

  • Worst/avg: O(n²), Best: O(n)
  • Space: O(1) | Stable: Yes
  • Best for nearly sorted data

insert into sorted portion

Of the three, Insertion Sort is generally the best choice. It is fast on nearly sorted data, stable, and has a good best-case.

Examples

Already Sorted Data — Best Case

pseudocode
1
2
3
4
5
6
7
8
Input: [1, 2, 3, 4, 5]
​
i=1: key=2. arr[0]=1 > 2? No. No shifts. Place 2.
i=2: key=3. arr[1]=2 > 3? No. No shifts. Place 3.
i=3: key=4. arr[2]=3 > 4? No. No shifts. Place 4.
i=4: key=5. arr[3]=4 > 5? No. No shifts. Place 5.
​
Total shifts: 0. Total comparisons: 4. Time: O(n).

Reverse Sorted Data — Worst Case

pseudocode
1
2
3
4
5
6
7
8
Input: [5, 4, 3, 2, 1]
​
i=1: key=4. Shift 5. -> [4, 5, 3, 2, 1]   (1 shift)
i=2: key=3. Shift 5, 4. -> [3, 4, 5, 2, 1] (2 shifts)
i=3: key=2. Shift 5,4,3. -> [2, 3, 4, 5, 1] (3 shifts)
i=4: key=1. Shift 5,4,3,2. -> [1,2,3,4,5]  (4 shifts)
​
Total shifts: 1+2+3+4 = 10. Time: O(n²).

Common Mistakes

  1. Starting the outer loop at index 0. Index 0 is already "sorted" (one element is trivially sorted). Start at index 1.
  1. Using >= instead of > in the comparison. Using arr[j] >= key makes the sort unstable — equal elements get rearranged unnecessarily. Always use strict greater-than.
  1. Forgetting to save the key before shifting. Shifting arr[i] to the right overwrites it. You must save key = arr[i] at the start of each outer loop iteration.
  1. Off-by-one in the insertion position. After the while loop ends, the key goes at j + 1, not j. The loop stopped because arr[j] is no longer greater than key — so the key goes just to the right of j.

Best Practices

  • Use Insertion Sort for small arrays (fewer than about 20 elements). It is faster in practice than O(n log n) algorithms for tiny inputs due to low overhead.
  • Use Insertion Sort when data arrives one item at a time. Each new item gets inserted into the already-sorted portion immediately.
  • Prefer Insertion Sort when stability matters and you need a simple O(n²) sort.
  • In interviews, mention the O(n) best case. It shows you know Insertion Sort is adaptive — it takes advantage of existing order in the data.
Bubble Sort and Selection SortMerge Sort and Quick Sort