Insertion Sort Explained: A Step-by-Step Technical Guide

Insertion Sort is an elegant simplicity and practical, real-world utility.

What is an Insertion Sort?

Imagine you’re dealt a hand of playing cards. To sort them, you don’t spread them all over the table. Instead, you keep a sorted group on the left, pick up one unsorted card at a time, and slide it directly into its rightful spot, shifting the other cards over to make room.

That is exactly how Insertion Sort works. It is a highly intuitive, comparison-based algorithm operating on the “incremental build” principle. Instead of trying to reorganize the entire array at once, it processes the list element-by-element, maintaining a sorted section on the left and sliding each new element from the unsorted right section into its proper place.

Because it performs these quick, local shifts entirely “in-place,” it requires absolutely zero extra memory workspace (O(1) auxiliary space), making it incredibly lightweight.

Why it’s better than Selection or Bubble Sort: While Bubble Sort mindlessly swaps elements back and forth and Selection Sort stubbornly scans the entire remaining list every single time, Insertion Sort is brilliantly adaptive. If your data is already nearly sorted, it barely glances at it, running at a lightning-fast linear speed (O(n)). It is so efficient on a small scale that high-powered algorithms like Merge Sort actually hand off their final, small-scale sorting steps to Insertion Sort to finish the job.

What are its characteristics?

• Super Stable Sorting

Insertion Sort preserves the original order of duplicate values. When sliding a number into the sorted section, the algorithm stops shifting the moment it hits an equal value. Because identical numbers never leapfrog over each other, your data stays perfectly consistent.

• Zero Extra Space (O(1) Space)

This is an “in-place” algorithm that sorts your data directly inside the original list. It requires virtually zero extra memory, using just a single temporary variable to hold one number while shifting others. This makes it incredibly lightweight and perfect for systems with strict memory limits.

• Smart, Adaptive Speed

The algorithm’s speed dynamically adapts to how organized your data already is. If the list is already sorted, it glides through in a single quick pass at lightning-fast linear speed. However, if the list is completely backward, it is forced to shift every single number, dropping its performance to a slow quadratic pace.

• Time and Space Complexity

• Best Case: O(n) -> Already sorted data (one quick scan, zero shifting).
• Worst/Average Case: O($n^2$) -> Reverse or randomized data (heavy, repetitive shifting).
• Space Complexity: O(1) -> Entirely in-place with no extra helper arrays needed.

(Note: While slow for massive datasets, Insertion Sort is extremely fast for small lists (under 15 items) and nearly sorted data. In fact, major programming languages like Python and Java use hybrid algorithms (like Timsort) that automatically switch to Insertion Sort to finish up the final, small-scale sorting.)

Step-By-Step Example

Let’s see how Insertion Sort works on a array: [8, 3, 1, 9, 5, 4].

We start with the first element (8) as our sorted section, and process the rest one by one.

• Step 1: Sort the 2nd element (Key = 3)

Array: [8, 3, 1, 9, 5, 4].

1. Compare 3 with 8.
2. Since 8 is greater than 3, we shift 8 to the right.
3. Insert 3 into the vacant first spot.
4. Result: [3, 8, 1, 9, 5, 4]

• Sort the 3rd element (Key = 1)

Array: [3, 8, 1, 9, 5, 4].

1. Compare 1 with 8 (shift 8) and then with 3 (shift 3).
2. Since both are greater than 1, we shift both to the right.
3. Insert 1 at the very beginning.
4. Result: [1, 3, 8, 9, 5, 4]

• Sort the 4th element (Key = 9)

Array: [1, 3, 8, 9, 5, 4].

1. Compare 9 with the sorted neighbor 8.
2. Since 8 is less than 9, no shifting is needed.
3. 9 stays right where it is.
4. Result: [1, 3, 8, 9, 5, 4]

• Sort the 5th element (Key = 5)

Array: [1, 3, 8, 9, 5, 4].

1. Compare 5 with 9 (shift 9) and 8 (shift 8).
2. When we compare 5 with 3, we stop because 3 is less than 5.
3. Insert 5 into the gap right after 3.
4. Result: [1, 3, 5, 8, 9, 4]

• Sort the 6th element (Key = 4)

Array: [1, 3, 5, 8, 9, 4].

1. Compare 4 with 9 (shift 9), 8 (shift 8), and 5 (shift 5).
2. Stop comparing when we hit 3 (since 3 is less than 4).
3. Insert 4 into the gap right after 3.
4. Result: [1, 3, 4, 5, 8, 9] (Fully Sorted!)

Here is the implementation of Insertion Sort in C++

#include <iostream>
#include <vector>

// Function to perform Insertion Sort
void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    
    // Start from the second element (index 1)
    for (int i = 1; i < n; ++i) {
        int key = arr[i]; // The element we are currently positioning
        int j = i - 1;

        // Shift elements of arr[0..i-1] that are greater than the key
        // to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        
        // Insert the key into its correct sorted position
        arr[j + 1] = key;
    }
}

// Helper function to print the array
void printArray(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << "\n";
}

int main() {
    // 6-digit array from our step-by-step example
    std::vector<int> arr = {8, 3, 1, 9, 5, 4};

    std::cout << "Original array: ";
    printArray(arr);

    insertionSort(arr);

    std::cout << "Sorted array:   ";
    printArray(arr);

    return 0;
}

This will sort the array, in Ascending Order.

But what will be the code in Descending Order? Like almost other sorting techniques, there is just another slight change!

// Change this:
while (j >= 0 && arr[j] > key)

// To this:
while (j >= 0 && arr[j] < key)

What are Insertion Sort’s Advantages?

1. Extremely Memory-Efficient (O(1) Space): It is a strictly in-place algorithm. It rearranges the elements directly within the original array, requiring no extra helper arrays. This makes it ideal for systems with very limited RAM (like embedded systems or microcontrollers).
2. Highly Adaptive (Super Fast for “Nearly Sorted” Data): If the input data is already sorted, or almost sorted, Insertion Sort runs in linear time O(n). It quickly checks the elements and does virtually no shifting.
3. The Micro-Scale Champion: Because it has no complex recursion or partition overhead, it is incredibly fast for small datasets (typically fewer than 15 elements). It easily beats heavy-duty algorithms like Merge Sort or Quick Sort on this scale.
4. Online Sorting Capability: It can sort data in real-time as it arrives. If you are streaming data, you can insert new elements one by one directly into the already-sorted portion without having to restart the sorting process.
5. Perfect Stability: It is a stable sort, meaning it preserves the original relative order of duplicate elements. This is crucial when sorting database records by multiple criteria.

Similarly, It’s disadvantages include-

1. Terrible Scalability (O($n^2$) Worst/Average Case): Because of its quadratic time complexity, its performance plummets drastically as the dataset grows. Sorting 10,000 elements will take millions of operations, making it entirely useless for large-scale data.
2. Brutal on Reverse-Sorted Data: If you feed it a list that is in absolute reverse order, it suffers its absolute worst-case performance. It is forced to compare and shift every single element all the way back to the beginning of the array on every single pass.
3. Excessive Writing/Shifting Operations: Unlike Selection Sort (which only makes a maximum of O(n) swaps), Insertion Sort has to constantly shift elements over one by one to make room for the key. If writing to memory is “expensive” or slow on your hardware, these constant write operations can bottleneck performance.

So conclusively, Use Insertion Sort if: You are dealing with small arrays, streaming data on the fly, working with nearly-sorted lists, or writing code for a system with strict memory limits, and Avoid it if: You have a large, unpredictable, or completely randomized dataset where a O(n log n) algorithm like Merge Sort or Quick Sort is required.