Offensive Security Researcher & Quantum Cryptography Analyst

Insertion Sort Algorithm: Analysis, Design, and Implementation Guide

Abdul Wahab Junaid
Insertion Sort, Algorithm Analysis, and Design

Insertion sort is usually the very first sorting algorithm I encounter when learning algorithms, and I still think it’s one of the best starting points, not because it’s the fastest, but because it mirrors something I already do naturally — sorting a hand of playing cards by picking up each new card and inserting it into its correct position among the cards I’m already holding. It’s simple enough to fully understand in one sitting, yet rich enough to teach me the core tools of algorithm analysis: loop invariants, worst/average/best-case reasoning, and asymptotic notation.

History and Background

Insertion sort is one of the oldest and most intuitive sorting algorithms, with roots that predate modern computing entirely — it formalizes a sorting strategy humans have used manually for a very long time, such as sorting cards by hand. As a formally studied computer algorithm, it appears in early computer science texts from the 1950s and 1960s and is discussed extensively by Donald Knuth in The Art of Computer Programming, Volume 3: Sorting and Searching (1973), where he analyzes it alongside other classical sorting methods. It remains a standard opening example in nearly every algorithms textbook, including CLRS, precisely because of its simplicity and intuitive correctness argument.

Problem Statement

Given an array of $n$ elements, I want to rearrange them into sorted order (typically ascending), using a method that builds up the sorted portion of the array incrementally, one element at a time.

Core Concepts

How It Works

  1. I start by considering the first element as trivially “sorted” (a sorted region of size 1).
  2. For each subsequent element (starting from index 1), I call it the “key.”
  3. I compare the key against the elements in the sorted region, moving from right to left.
  4. I shift each element in the sorted region that’s greater than the key one position to the right.
  5. I stop shifting once I find an element smaller than or equal to the key, or I reach the beginning of the array.
  6. I insert the key into the now-vacated position.
  7. I repeat this process for every element until the entire array is sorted.

Working Principle

The internal mechanism relies on maintaining the invariant that the subarray to the left of the current position is always fully sorted. Each iteration extends this sorted region by exactly one element, using a linear scan-and-shift process to place the new element in its correct spot. Because I only need to compare the new element against already-sorted elements (rather than the entire array), and because I can stop shifting early once I find the correct position, the algorithm can be quite fast on data that’s already nearly sorted.

Mathematical Foundation

Loop invariant proof of correctness:

Time complexity derivation:

For each element at position $j$ (from 2 to $n$), in the worst case (array sorted in reverse), the number of comparisons and shifts is $j – 1$. Summing over all $j$:

$$ \sum_{j=2}^{n} (j-1) = \sum_{k=1}^{n-1} k = \frac{(n-1)n}{2} = \Theta(n^2) $$

In the best case (already sorted array), each element requires only 1 comparison and 0 shifts, giving:

$$ \sum_{j=2}^{n} 1 = n – 1 = \Theta(n) $$

For the average case, assuming a random permutation, each element is expected to require about $j/2$ comparisons, giving:

$$ \sum_{j=2}^{n} \frac{j}{2} = \Theta(n^2) $$

Diagrams

flowchart TD
    A["Start: sorted region = [A[0]]"] --> B["Take next element as key"]
    B --> C{"key < element to its left in sorted region?"}
    C -- Yes --> D["Shift that element one position right"]
    D --> C
    C -- No --> E["Insert key into vacated position"]
    E --> F{"More elements remaining?"}
    F -- Yes --> B
    F -- No --> G["Array is fully sorted"]

Pseudocode

INSERTION-SORT(A, n):
    for j = 2 to n:
        key = A[j]
        i = j - 1
        while i > 0 and A[i] > key:
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key

Step-by-Step Example

Let me sort the array [5, 2, 4, 6, 1, 3] step by step.

Time Complexity

Space Complexity

Insertion sort is an in-place algorithm, requiring only $O(1)$ auxiliary space beyond the input array itself, since it only needs a constant number of extra variables (the key and loop indices) regardless of input size.

Correctness Analysis

I’ve already sketched the loop invariant proof above, which is the standard method for proving insertion sort’s correctness: I show the invariant (the processed prefix is sorted) holds at initialization, is maintained through each iteration, and implies the desired outcome upon termination. This three-part structure — initialization, maintenance, termination — mirrors mathematical induction and is a technique I can reuse for proving the correctness of many other iterative algorithms.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>

/* Sorts an array of n integers in ascending order using insertion sort. */
void insertionSort(int A[], int n) {
    for (int j = 1; j < n; j++) {
        int key = A[j];        /* the element I'm currently inserting */
        int i = j - 1;

        /* shift elements greater than key one position to the right */
        while (i >= 0 && A[i] > key) {
            A[i + 1] = A[i];
            i = i - 1;
        }
        A[i + 1] = key;        /* insert key into its correct position */
    }
}

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

int main() {
    int A[] = {5, 2, 4, 6, 1, 3};
    int n = sizeof(A) / sizeof(A[0]);

    printf("Before sorting: ");
    printArray(A, n);

    insertionSort(A, n);

    printf("After sorting:  ");
    printArray(A, n);

    return 0;
}

Sample Input and Output

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

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version