Offensive Security Researcher & Quantum Cryptography Analyst

Insertion Sort Algorithm: Working, Explanation, and Simple Sorting Method

Abdul Wahab Junaid
insertion sort algorithm and working of this algorithm

I always compare insertion sort to how I naturally sort a hand of playing cards — I pick up one card at a time and slide it into its correct position among the cards I am already holding. That is exactly what insertion sort does with an array: it builds up a sorted section one element at a time, inserting each new element into its correct place among the elements already sorted. It is a simple, comparison-based, in-place sorting algorithm with O(n²) worst-case time complexity, but I value it highly for its efficiency on small or nearly-sorted datasets, and for being one of the few sorting algorithms that is both stable and adaptive.

History and Background

Insertion sort is one of the oldest and most naturally derived sorting techniques, with no single credited inventor, since it reflects a manual sorting process humans have used for centuries — well before computers existed. It has been formally documented in computer science literature since the earliest algorithm textbooks of the 1950s and 60s, and it remains a staple teaching example because of how closely it mirrors intuitive, real-world sorting behavior. Its practical relevance persists today: modern hybrid sorting algorithms like Timsort (used in Python and Java) and Introsort variants explicitly fall back to insertion sort for small subarrays because of its excellent low-overhead performance at small scales.

Problem Statement

I need a sorting algorithm that performs exceptionally well on small datasets or data that is already nearly sorted, without the overhead of more complex divide-and-conquer algorithms. Insertion sort addresses this by processing elements one at a time, inserting each into its correct position relative to the already-sorted prefix, achieving near-linear performance when the input requires only a small number of shifts.

Core Concepts

How It Works

I proceed through the array like this:

  1. I consider the first element as trivially sorted by itself.
  2. I take the next element (the “key”) from the unsorted region.
  3. I compare the key with elements in the sorted region, moving from right to left, shifting each larger element one position to the right to make room.
  4. I insert the key into the gap created once I find an element smaller than or equal to it (or I reach the start of the array).
  5. I repeat this process for each remaining element until the entire array is sorted.

Working Principle

The mechanism I depend on is maintaining a strict invariant: at every point during the algorithm, the elements to the left of my current position form a fully sorted subarray. When I bring in the next key, I only need to find its correct place within that already-sorted prefix — I don’t need to re-examine the entire array, just scan backward until I find where the key fits. This backward scan-and-shift approach is what gives insertion sort its adaptive nature: if the key is already larger than everything before it, the scan terminates immediately, requiring almost no work.

Mathematical Foundation

For an array of size n, the number of comparisons and shifts insertion sort performs depends heavily on the initial order of the data. In the worst case (reverse-sorted input), inserting the i-th element requires shifting through all i previously sorted elements:

$$\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}$$

giving:

$$T_{worst}(n) = O(n^2)$$

In the best case (already sorted input), each key only requires a single comparison to confirm its place, giving:

$$T_{best}(n) = O(n)$$

The average case, assuming a uniformly random permutation of the input, involves each element needing to move roughly half the distance of the worst case on average:

$$T_{avg}(n) = O(n^2)$$

though with a smaller constant factor than the worst case, since:

$$E[\text{shifts for element } i] = \frac{i}{2}$$

Diagrams

flowchart TD
    A[Start: Unsorted array] --> B[Consider first element sorted]
    B --> C[Take next element as key]
    C --> D[Compare key with sorted elements, right to left]
    D --> E{Element greater than key?}
    E -->|Yes| F[Shift element one position right]
    F --> D
    E -->|No| G[Insert key into the gap]
    G --> H{More elements?}
    H -->|Yes| C
    H -->|No| I[Output: Sorted array]
graph LR
    A["[5,2,4,6,1,3]"] -->|"insert 2"| B["[2,5,4,6,1,3]"]
    B -->|"insert 4"| C["[2,4,5,6,1,3]"]
    C -->|"insert 6"| D["[2,4,5,6,1,3]"]
    D -->|"insert 1"| E["[1,2,4,5,6,3]"]
    E -->|"insert 3"| F["[1,2,3,4,5,6]"]

Pseudocode

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

Step-by-Step Example

I will sort [5, 2, 4, 6, 1, 3].

i=1, key=2: Compare with A[0]=5. 5 > 2, shift → [5,5,4,6,1,3], j=-1. Insert key at position 0 → [2,5,4,6,1,3]

i=2, key=4: Compare with A[1]=5. 5 > 4, shift → [2,5,5,6,1,3], j=0. Compare with A[0]=2. 2 not > 4, stop. Insert key at position 1 → [2,4,5,6,1,3]

i=3, key=6: Compare with A[2]=5. 5 not > 6, stop immediately. Insert key at position 3 (no shift needed) → [2,4,5,6,1,3]

i=4, key=1: Compare with A[3]=6, shift; A[2]=5, shift; A[1]=4, shift; A[0]=2, shift → [2,2,4,5,6,3]→ after shifts → [_,2,4,5,6,3] conceptually, j=-1. Insert key at position 0 → [1,2,4,5,6,3]

i=5, key=3: Compare with A[4]=6, shift; A[3]=5, shift; A[2]=4, shift; A[1]=2, 2 not > 3, stop. Insert key at position 2 → [1,2,3,4,5,6]

Final sorted output: [1, 2, 3, 4, 5, 6]

Time Complexity

Space Complexity

Insertion sort is fully in-place, requiring only O(1) additional space for the key variable and loop indices used during shifting. It needs no auxiliary array, which makes it as memory-efficient as selection sort while also offering the benefit of adaptiveness.

Correctness Analysis

I prove insertion sort’s correctness using a loop invariant: at the start of each iteration of the outer loop (indexed by i), the subarray A[0..i-1] consists of the same elements originally in that position, but rearranged into sorted order. This holds trivially at the start, since a single-element subarray A[0..0] is trivially sorted. During each iteration, I insert A[i] into its correct position within the already-sorted A[0..i-1] by shifting all elements greater than the key one position to the right and placing the key into the resulting gap — this preserves the sorted property and extends the invariant to A[0..i]. When the outer loop terminates after processing index n-1, the invariant guarantees the entire array A[0..n-1] is sorted.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>

// Insertion sort implementation
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];   // element to be inserted
        int j = i - 1;

        // Shift elements of the sorted region that are greater than key
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // Insert key into its correct position
        arr[j + 1] = key;
    }
}

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

    insertionSort(arr, n);

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

    return 0;
}

Sample Input and Output

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

Output: Sorted array: 1 2 3 4 5 6

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version