Chapter 17 of 65

Insertion Sort

Imagine you're playing cards. The dealer hands you one card at a time, and you keep the cards in your hand sorted.

Every time you get a new card, you don't re-sort the whole hand. You simply slide the new card left until it sits in the right place.

Hand:      [3, 7, 9]
New card:  5

Slide 5 left past 9, past 7, stop at 3

Hand:      [3, 5, 7, 9]

That's exactly how Insertion Sort works.

Insertion Sort builds the sorted array one element at a time by taking the next element and inserting it into its correct position among the elements that are already sorted.

Insertion Sort is simple like Bubble Sort and Selection Sort, but it has some special strengths: it is very fast on nearly sorted data, it is stable, and real-world sorting libraries still use it for small arrays.


The Core Idea

Insertion Sort divides the array into two parts:

[ sorted part | unsorted part ]

At the start, the sorted part contains only the first element. A single element is always sorted.

[5 | 2, 4, 6, 1, 3]
 ↑
sorted

Then, one by one, we pick the first element of the unsorted part (called the key) and insert it into the correct position in the sorted part.

Pick key
   ↓
Compare it with elements on its left
   ↓
Shift every bigger element one step right
   ↓
Drop the key into the gap
   ↓
Sorted part grows by one

After processing every element, the whole array is sorted.


Shifting, Not Swapping

This is the detail that makes Insertion Sort efficient.

Suppose the sorted part is [2, 4, 5, 6] and the key is 1.

We first save the key in a variable:

key = 1

[2, 4, 5, 6, 1]

Then we shift every element bigger than the key one position to the right:

6 > 1 → shift   [2, 4, 5, 6, 6]
5 > 1 → shift   [2, 4, 5, 5, 6]
4 > 1 → shift   [2, 4, 4, 5, 6]
2 > 1 → shift   [2, 2, 4, 5, 6]

We have reached the beginning of the array, so we place the key in the gap:

[1, 2, 4, 5, 6]

The duplicates you see in the middle are temporary. Because we saved the key first, nothing is lost.

Each shift is one assignment, while a swap needs three. That's why the standard version shifts instead of swapping.


Step-by-Step Example

Let's sort:

[5, 2, 4, 6, 1, 3]

Pass 1 (key = 2)

Sorted part: [5]

5 > 2 → shift 5 right
Reached the start → insert 2

[2, 5, 4, 6, 1, 3]

Pass 2 (key = 4)

Sorted part: [2, 5]

5 > 4 → shift 5 right
2 < 4 → stop, insert 4 after 2

[2, 4, 5, 6, 1, 3]

Pass 3 (key = 6)

Sorted part: [2, 4, 5]

5 < 6 → stop immediately (no shifts)

[2, 4, 5, 6, 1, 3]

Notice that when the key is already bigger than everything before it, the pass costs just one comparison.

Pass 4 (key = 1)

Sorted part: [2, 4, 5, 6]

6, 5, 4, 2 are all bigger → shift all four
Reached the start → insert 1

[1, 2, 4, 5, 6, 3]

Pass 5 (key = 3)

Sorted part: [1, 2, 4, 5, 6]

6 > 3 → shift
5 > 3 → shift
4 > 3 → shift
2 < 3 → stop, insert 3 after 2

[1, 2, 3, 4, 5, 6]

The array is sorted after n - 1 = 5 passes.


Insertion Sort in Java

Here's the complete program. It also prints the array after every pass so you can match it with the trace above.

import java.util.Arrays;

class Main {

    static void insertionSort(int[] arr) {

        int n = arr.length;

        for (int i = 1; i < n; i++) {

            int key = arr[i];
            int j = i - 1;

            // Shift bigger elements one position to the right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            // Drop the key into the gap
            arr[j + 1] = key;

            System.out.println("After pass " + i + ": "
                + Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {

        int[] arr = {5, 2, 4, 6, 1, 3};

        System.out.println("Original:     "
            + Arrays.toString(arr));

        insertionSort(arr);

        System.out.println("Sorted:       "
            + Arrays.toString(arr));
    }
}

Output:

Original:     [5, 2, 4, 6, 1, 3]
After pass 1: [2, 5, 4, 6, 1, 3]
After pass 2: [2, 4, 5, 6, 1, 3]
After pass 3: [2, 4, 5, 6, 1, 3]
After pass 4: [1, 2, 4, 5, 6, 3]
After pass 5: [1, 2, 3, 4, 5, 6]
Sorted:       [1, 2, 3, 4, 5, 6]

Understanding the Code

The outer loop starts at index 1, not 0:

for (int i = 1; i < n; i++)

because the first element alone is already a sorted part.

We save the current element before anything overwrites it:

int key = arr[i];

The inner loop walks left through the sorted part:

while (j >= 0 && arr[j] > key)

It stops for one of two reasons:

j < 0          → we passed the start of the array
arr[j] <= key  → we found an element that is not bigger

In both cases, the correct position for the key is j + 1:

arr[j + 1] = key;

The loop invariant is worth remembering for interviews:

At the start of each pass i, the subarray arr[0..i-1] contains the original first i elements, in sorted order.


Time Complexity

The amount of work depends heavily on how the input is arranged. Let's count the actual comparisons and shifts for three arrays of size 8:

class Main {

    static void countWork(String label, int[] arr) {

        int comparisons = 0;
        int shifts = 0;

        for (int i = 1; i < arr.length; i++) {

            int key = arr[i];
            int j = i - 1;

            while (j >= 0) {
                comparisons++;

                if (arr[j] > key) {
                    arr[j + 1] = arr[j];
                    shifts++;
                    j--;
                } else {
                    break;
                }
            }

            arr[j + 1] = key;
        }

        System.out.println(label + " -> comparisons = "
            + comparisons + ", shifts = " + shifts);
    }

    public static void main(String[] args) {

        countWork("Sorted   ", new int[]{1, 2, 3, 4, 5, 6, 7, 8});
        countWork("Random   ", new int[]{3, 7, 1, 8, 2, 6, 4, 5});
        countWork("Reversed ", new int[]{8, 7, 6, 5, 4, 3, 2, 1});
    }
}

Output:

Sorted    -> comparisons = 7, shifts = 0
Random    -> comparisons = 19, shifts = 13
Reversed  -> comparisons = 28, shifts = 28

Best Case: Already Sorted

Every key is already bigger than the element before it, so each pass does exactly one comparison and zero shifts.

Comparisons = n - 1 = 7
Time        = O(n)

Worst Case: Reverse Sorted

Every key is smaller than everything before it, so it travels all the way to the front.

Comparisons = 1 + 2 + ... + (n - 1)
            = n(n - 1) / 2
            = 8 × 7 / 2 = 28

Time = O(n²)

Average Case

On random data, a key moves about halfway back on average, which is still about n² / 4 comparisons:

Time = O(n²)

Shifts = Inversions

Here's a neat fact. An inversion is a pair of positions (i, j) with i < j but arr[i] > arr[j], a pair that is "out of order".

Each shift fixes exactly one inversion. So:

The number of shifts Insertion Sort performs equals the number of inversions in the array.

The random array [3, 7, 1, 8, 2, 6, 4, 5] has 13 inversions, which is exactly the 13 shifts in the output above. A nearly sorted array has very few inversions, so Insertion Sort finishes in almost linear time.

Space Complexity

We only use a few variables (key, i, j), so:

Space = O(1)   (in-place)

Case

Time

When it happens

Best

O(n)

Already sorted

Average

O(n²)

Random order

Worst

O(n²)

Reverse sorted

Space

O(1)

Always


Insertion Sort Is Stable

A sorting algorithm is stable if elements with equal keys keep their original relative order.

Insertion Sort is stable because the inner loop uses a strict comparison:

arr[j] > key

An element equal to the key is never shifted past it.

Let's sort students by marks. Riya and Dev both have 72, and Aman and Kabir both have 85:

class Main {

    static void insertionSortByMarks(String[] names, int[] marks) {

        for (int i = 1; i < marks.length; i++) {

            int keyMarks = marks[i];
            String keyName = names[i];
            int j = i - 1;

            // Strictly greater: equal marks are NOT moved
            while (j >= 0 && marks[j] > keyMarks) {
                marks[j + 1] = marks[j];
                names[j + 1] = names[j];
                j--;
            }

            marks[j + 1] = keyMarks;
            names[j + 1] = keyName;
        }
    }

    public static void main(String[] args) {

        String[] names = {"Aman", "Riya", "Kabir", "Sneha", "Dev"};
        int[] marks    = {  85,     72,     85,      60,     72 };

        insertionSortByMarks(names, marks);

        for (int i = 0; i < names.length; i++) {
            System.out.println(names[i] + " " + marks[i]);
        }
    }
}

Output:

Sneha 60
Riya 72
Dev 72
Aman 85
Kabir 85

Riya still comes before Dev, and Aman still comes before Kabir, just like in the original input.

If you change > to >=, the array is still sorted, but equal elements get reversed and the sort is no longer stable.


Other Useful Properties

Adaptive

An algorithm is adaptive if it runs faster when the input is already partly sorted. Insertion Sort is a perfect example: its running time is O(n + inversions).

Online

Insertion Sort is online: it can sort data as it arrives, without seeing the whole input first. Each new element is simply inserted into the already sorted part, just like picking up cards one at a time.

Used Inside Real Sorting Libraries

For very small arrays, Insertion Sort beats O(n log n) algorithms because it has almost no overhead. That's why hybrid algorithms use it for small pieces:

  • Java's Arrays.sort() for objects uses TimSort, which uses (binary) insertion sort to build short sorted runs.

  • Java's Arrays.sort() for primitives uses Dual-Pivot Quicksort, which switches to insertion sort for tiny subarrays.

  • Python's built-in sorted() also uses insertion sort for short runs.


Binary Insertion Sort

Since the left part is always sorted, we could use Binary Search to find where the key belongs, instead of comparing one by one.

Comparisons per pass → O(log n)  (instead of O(n))

However, we still have to shift all the bigger elements to make room. In the worst case, that's still O(n) shifts per pass.

Total time → still O(n²)

Binary insertion sort helps when comparisons are expensive (for example, comparing long strings or complex objects), but it does not change the overall Big O.


Common Mistakes

1. Wrong order of conditions in the while loop

// Wrong: arr[-1] is accessed when j becomes -1
while (arr[j] > key && j >= 0)

// Correct: check the index first
while (j >= 0 && arr[j] > key)

Java's && is short-circuit, so checking j >= 0 first prevents an ArrayIndexOutOfBoundsException.

2. Not saving the key

If you write arr[j + 1] = arr[j] without saving arr[i] first, the first shift overwrites the key and its value is lost.

3. Placing the key at arr[j] instead of arr[j + 1]

When the loop ends, j points to the element that is not bigger than the key (or to -1). The gap is one step to its right.

4. Using >= instead of >

The result is still sorted, but the sort becomes unstable and does extra shifts for duplicates.

5. Starting the outer loop at 0

It works, but the first pass does nothing useful. Start at 1.


Insertion vs Bubble vs Selection

All three are simple O(n²) algorithms, but they behave differently:

Property

Bubble Sort

Selection Sort

Insertion Sort

Best case

O(n) (with swapped flag)

O(n²)

O(n)

Average / Worst

O(n²)

O(n²)

O(n²)

Space

O(1)

O(1)

O(1)

Stable

Yes

No (standard version)

Yes

Writes to array

Many swaps

At most n - 1 swaps

One write per shift

Adaptive

Yes (with flag)

No

Yes

In practice, Insertion Sort is usually the fastest of the three. Selection Sort is only preferred when writing to memory is very expensive, because it does the fewest swaps.


When Should You Use Insertion Sort?

Good choices:

  • Small arrays (roughly a few dozen elements)

  • Nearly sorted arrays

  • Data arriving one element at a time (online sorting)

  • When you need a stable, in-place sort with simple code

  • As the "small case" inside a faster hybrid sort

Bad choices:

  • Large random or reverse-sorted arrays, where O(n²) becomes too slow. Use Merge Sort or Quick Sort (coming up next) instead.


Interview Tips and Practice

Questions interviewers like to ask:

  • Why is Insertion Sort O(n) on sorted input? Because each pass stops after one comparison.

  • How many shifts does it do? Exactly the number of inversions.

  • Why do libraries still use it? It has tiny overhead, so it is fastest for small or nearly sorted inputs.

  • Does binary search make it O(n log n)? No, shifting is still O(n²) in the worst case.

Practice problems:

  • Insertion Sort List (LeetCode 147): apply the same idea to a linked list, after you learn Linked Lists.

  • Sort an array of 0s, 1s and 2s using insertion sort, then compare with better approaches.

  • Count the number of inversions in an array using insertion sort (you'll learn a faster way in Merge Sort).

  • Sort a "k-sorted" array, where every element is at most k positions away from its final place. Insertion Sort solves it in O(n·k).


The Main Idea

Insertion Sort keeps a sorted part on the left and inserts each new element into its correct place by shifting bigger elements to the right.

Pick key
   ↓
Shift bigger elements right
   ↓
Insert key into the gap
   ↓
Repeat for every element

Its key facts:

Best    → O(n)    (already sorted)
Average → O(n²)
Worst   → O(n²)   (reverse sorted)
Space   → O(1)
Stable  → Yes
Adaptive and Online → Yes

Insertion Sort is the best simple sorting algorithm for small or nearly sorted data, which is why even modern hybrid sorts rely on it for small pieces of the array.

In the next chapter, we'll see Merge Sort, which breaks the O(n²) barrier by splitting the problem in half again and again.