Insertion Sort

Say you have a list of numbers and you want them in order. You could compare every pair and swap them around, but that feels messy, right? Insertion sort gives you a cleaner way. It picks up one item at a time and slides it into the right place among the items you have already sorted.

🃏 Think of Sorting Cards in Your Hand

Picture this. You are playing cards. The dealer gives you cards one by one and you keep them sorted in your hand.

You pick up the first card. Nothing to compare, so it just sits there. Then comes the second card. You look at it and slide it left or right so the two cards are in order. The third card arrives, and you push it into its correct spot among the two you already arranged.

That is exactly what insertion sort does. Insertion sort is a method that builds the sorted list one item at a time by taking the next item and placing it into its correct position among the already-sorted items.

The left part of your hand is always sorted. The right part is the pile you still need to deal with. Every new card moves from the unsorted pile into the sorted part.

🎯 What Problem Does It Solve?

Imagine a list that is already almost in order. Maybe one or two items are out of place. A heavy sorting method would still do a lot of work here, even though the list is almost done. That wastes time.

Insertion sort is great in this case. When the data is nearly sorted, it barely does any work. It walks through the list. It sees most items are already fine. It only nudges the few that are out of place.

So insertion sort is a good pick when:

• The list is small.
• The list is already nearly sorted.
• You want something simple to write and easy to understand.

🧠 How It Works

Let us sort this small list: [5, 2, 4, 6, 1].

The idea is simple. We treat the first item as a sorted part of size one. Then we pick the next item, call it the key, and shift bigger items to the right to make room for it.

Here is the flow for one round:

Let us watch the list change step by step. The part in bold is the sorted region.

See how 6 did not move? It was already bigger than everything on its left, so it stayed put. That is the quick exit insertion sort takes when items are in order.

📝 Steps to Do Insertion Sort

Before we write code, let us lay out the steps in plain words.

1. Start from the second item. The first item is a sorted part by itself.
2. Store the current item in a variable called key.
3. Look at the items to the left of key, one by one, going leftward.
4. As long as a left item is bigger than key, shift that item one step to the right.
5. When you find an item that is not bigger (or you reach the start), drop key into the gap.
6. Move to the next item and repeat until the list ends.

💻 Insertion Sort in Code

Now let us turn those steps into code. The function takes a list, sorts it in place, and we print it before and after.

#include <stdio.h>

// Sort the array in place using insertion sort
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];      // the item we want to place
        int j = i - 1;
        // shift bigger items one step to the right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;      // drop key into the gap
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {5, 2, 4, 6, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Before: ");
    printArray(arr, n);
    insertionSort(arr, n);
    printf("After:  ");
    printArray(arr, n);
    return 0;
}

Before: 5 2 4 6 1
After:  1 2 4 5 6

#include <iostream>
#include <vector>
using namespace std;

// Sort the vector in place using insertion sort
void insertionSort(vector<int>& arr) {
    for (size_t i = 1; i < arr.size(); i++) {
        int key = arr[i];      // the item we want to place
        int j = (int)i - 1;
        // shift bigger items one step to the right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;      // drop key into the gap
    }
}

void printArray(const vector<int>& arr) {
    for (int x : arr) cout << x << " ";
    cout << endl;
}

int main() {
    vector<int> arr = {5, 2, 4, 6, 1};
    cout << "Before: ";
    printArray(arr);
    insertionSort(arr);
    cout << "After:  ";
    printArray(arr);
    return 0;
}

Before: 5 2 4 6 1
After:  1 2 4 5 6

import java.util.Arrays;

public class InsertionSort {
    // Sort the array in place using insertion sort
    static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];      // the item we want to place
            int j = i - 1;
            // shift bigger items one step to the right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;      // drop key into the gap
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 1};
        System.out.println("Before: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("After:  " + Arrays.toString(arr));
    }
}

Before: [5, 2, 4, 6, 1]
After:  [1, 2, 4, 5, 6]

# Sort the list in place using insertion sort
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]          # the item we want to place
        j = i - 1
        # shift bigger items one step to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key      # drop key into the gap


numbers = [5, 2, 4, 6, 1]
print("Before:", numbers)
insertion_sort(numbers)
print("After: ", numbers)

Before: [5, 2, 4, 6, 1]
After:  [1, 2, 4, 5, 6]

// Sort the array in place using insertion sort
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];     // the item we want to place
    let j = i - 1;
    // shift bigger items one step to the right
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;       // drop key into the gap
  }
}

const numbers = [5, 2, 4, 6, 1];
console.log("Before:", numbers.join(" "));
insertionSort(numbers);
console.log("After: ", numbers.join(" "));

Before: 5 2 4 6 1
After:  1 2 4 5 6

⏱️ How Fast Is It?

The speed depends on how messy the list is to begin with.

Think about the worst case first. The list is in reverse order. Now every new item has to travel all the way to the front, shifting everything. That gives us O(n^2) time, which means the work grows with the square of the list size.

Now think about the best case. The list is already sorted. Each new item is checked once against its left neighbor, sees it is fine, and stops. That is just O(n) time, one pass through the list.

Here is the full picture in one table.

⚠️ Common Mistakes

A few small slips trip up most beginners. Watch out for these.

• Starting the outer loop at index 0 instead of 1. The first item is already a sorted part of size one, so you begin from the second item.
• Forgetting to place key after the loop. The line arr[j + 1] = key is what actually drops the item in. Miss it and the value is lost.
• Using arr[j] instead of key inside the while check. You stored the value in key for a reason. The slot arr[i] gets overwritten while you shift, so always compare against key.
• Writing j-- in the wrong spot. The shift arr[j + 1] = arr[j] must come before you move j left, or you copy the wrong value.

🧩 What You’ve Learned

✅ Insertion sort builds the sorted list one item at a time, like arranging cards in your hand.

✅ It picks each item as a key, shifts bigger items to the right, then drops the key into the gap.

✅ It runs in O(n) time on a sorted list and O(n^2) in the worst case, using only O(1) extra space.

✅ It is stable and a great choice for small or nearly sorted data.

🚀 What’s Next?

• Selection Sort
• Merge Sort