Insertion Sort in C, C++, Java: Code, Trace, Time Complexity

Insertion sort is the algorithm you use to put a new playing card into an already-sorted hand: pick the card, slide it left past every larger card, drop it in. That sentence is also the algorithm. The rest of this article is the price of writing it down precisely enough for a compiler and an interviewer.

The reason insertion sort still appears on placement question banks in 2026, despite being O(n^2) in the worst case, is the corner of its complexity profile that nothing else matches: O(n) on already-sorted input, O(1) extra memory, and a constant factor low enough that real-world standard library sorts switch to it for small subarrays. We’ll cover the trace, the code in three languages, the complexity, and the comparison with bubble, selection, merge, and quicksort below.

If you haven’t seen the related array fundamentals before, the warm-up exercise find the smallest and largest element in an array uses the same array-traversal vocabulary that this page assumes.

How insertion sort works

Insertion sort splits the input array into two regions: a sorted prefix on the left, and an unsorted suffix on the right. At every step it takes the first element of the unsorted suffix (call it the key), walks it leftward past every larger element in the sorted prefix, and drops it into place. After processing every index from 1 to n - 1, the prefix is the entire array and the suffix is empty.

Three things to notice before we look at code:

• The sorted prefix starts at length 1. A single element is trivially sorted.
• The “walk left” step does shifts, not swaps. Each larger element copies one position to the right; the key is written exactly once at the end.
• The inner loop stops as soon as it finds an element less than or equal to key. That early-exit is what makes the best case linear.

Step-by-step trace on [7, 1, 23, 4, 19]

The same input the standard FACE Prep walkthrough uses. Re-derived from first principles below, with comparisons and shifts counted explicitly so you can verify each row against the implementation later.

Iteration i	key	Array before	Comparisons	Shifts	Array after
1	1	[7, 1, 23, 4, 19]	1	1	[1, 7, 23, 4, 19]
2	23	[1, 7, 23, 4, 19]	1	0	[1, 7, 23, 4, 19]
3	4	[1, 7, 23, 4, 19]	3	2	[1, 4, 7, 23, 19]
4	19	[1, 4, 7, 23, 19]	2	1	[1, 4, 7, 19, 23]

Total work for this input: 7 comparisons, 4 shifts. The final sorted array is [1, 4, 7, 19, 23].

Iteration 2 is the one students miss in the trace. When key = 23, the very first comparison arr[1] > 23 evaluates to 7 > 23, which is false, so the while-loop never executes. Zero shifts. The array is unchanged. This is also the reason the best-case complexity is linear: on an already-sorted input, every iteration looks like iteration 2.

Pseudocode and the inner-loop invariant

The pseudocode below is the version most introductory algorithms courses use; it is the same one in the MIT 6.006 lecture notes, with the loop-invariant proof written out in full.

for i = 1 to n - 1
    key = arr[i]
    j   = i - 1

    while j >= 0 and arr[j] > key
        arr[j + 1] = arr[j]   # shift the larger element right
        j = j - 1

    arr[j + 1] = key          # drop key into its slot

The loop invariant: at the start of each iteration of the outer for, the subarray arr[0..i-1] contains the original elements of arr[0..i-1] in sorted order. Initialisation holds because arr[0..0] is one element. Maintenance holds because the inner while-loop shifts every element greater than key one slot right, then writes key into the gap. Termination: when i = n, the invariant says arr[0..n-1] is sorted, which is the whole array.

That three-line proof is what an interviewer means when they ask “how do you know your sort is correct?” Memorising “initialisation, maintenance, termination” is enough; the words map onto every loop-invariant proof you’ll write.

Implementation in C, C++, and Java

All three programs sort the same input [7, 1, 23, 4, 19] and print 1 4 7 19 23. The inner insertionSort body is identical across languages; only the I/O wrapping differs. C uses printf from <stdio.h>, C++ uses cout from <iostream>, Java uses System.out.print.

C implementation

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j   = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

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

int main(void) {
    int arr[] = {7, 1, 23, 4, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array: ");
    printArray(arr, n);
    return 0;
}

Output:

Sorted array: 1 4 7 19 23

C++ implementation

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j   = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {7, 1, 23, 4, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    cout << "Sorted array: ";
    printArray(arr, n);
    return 0;
}

Java implementation

class InsertionSort {
    static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j   = i - 1;

            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    static void printArray(int[] arr) {
        for (int num : arr) System.out.print(num + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {7, 1, 23, 4, 19};
        insertionSort(arr);
        System.out.print("Sorted array: ");
        printArray(arr);
    }
}

A small note on the comparison arr[j] > key: the strict > (rather than >=) is what makes the sort stable. If you swap it to >=, equal elements still get sorted correctly but their relative order can flip, and the algorithm is no longer stable.

Time and space complexity

The total work of insertion sort is dominated by the inner while-loop. For a fixed outer index i, the inner loop runs at most i times. Sum from i = 1 to n - 1 and you get the textbook n(n-1)/2, which is O(n^2). The best case collapses that sum because the inner loop exits after one comparison every time, giving O(n).

Case	Input shape	Comparisons	Shifts	Time	Space
Best	already sorted	n - 1	0	O(n)	O(1)
Average	random permutation	~n^2 / 4	~n^2 / 4	O(n^2)	O(1)
Worst	reverse sorted	n(n-1) / 2	n(n-1) / 2	O(n^2)	O(1)

Two implications recruiters like to probe:

• The number of comparisons in the worst case equals the number of inversions in the input. So insertion sort effectively counts inversions while it sorts. If a problem asks for the inversion count of a small array, insertion sort gives it for free.
• The space cost is O(1) because everything happens inside the input array. Three integer variables (i, j, key) is the entire auxiliary memory, regardless of n.

Insertion sort vs bubble, selection, merge, quick

Algorithm	Best	Average	Worst	Stable	Extra space	In-place
Insertion sort	O(n)	O(n^2)	O(n^2)	yes	O(1)	yes
Bubble sort	O(n)	O(n^2)	O(n^2)	yes	O(1)	yes
Selection sort	O(n^2)	O(n^2)	O(n^2)	no	O(1)	yes
Merge sort	O(n log n)	O(n log n)	O(n log n)	yes	O(n)	no
Quicksort	O(n log n)	O(n log n)	O(n^2)	no	O(log n)	yes

Insertion sort and bubble sort have identical big-O numbers, but insertion sort does fewer writes per pass on average. Bubble sort swaps three values per inversion; insertion sort shifts one. On modern CPUs the cache behaviour also favours insertion sort, which is one of the reasons standard libraries reach for it and not bubble sort when they need a small-n fallback.

When to actually use insertion sort

In production code, almost nobody calls insertion sort directly on a large array. The use cases that actually appear:

• Small inputs. For n smaller than roughly 16, the lower constant factor of insertion sort beats the recursion overhead of merge sort and quicksort. The OpenJDK implementation of Arrays.sort in DualPivotQuicksort.java hard-codes a small-array threshold (INSERTION_SORT_THRESHOLD) and switches to insertion sort below it. Python’s Timsort takes the same approach for runs shorter than its MIN_GALLOP window — see the CPython listsort.txt notes.
• Nearly sorted inputs. If the input is within a constant k of being sorted (every element is at most k positions from its final spot), insertion sort runs in O(nk). For small k, that beats O(n log n).
• Online sorting. Insertion sort handles a stream — when each new element arrives you insert it into the sorted prefix in O(n). Quicksort and merge sort have no equivalent for incremental input.
• Linked lists. On a singly linked list, the shift cost disappears: re-linking nodes is O(1) once the insertion point is known. The comparison count is unchanged.

In an interview, the right answer to “why would you use insertion sort?” is one of those four, with a number attached. “Because it’s simple” is not an answer; you’ll be asked which of the others you actually understand. The full menu of follow-up patterns lives in the data structures interview questions bank, which covers the modify-the-standard-implementation variants most assessments reuse.

A common variant: write insertion sort that sorts in descending order, or that sorts by a custom comparator. The change is one operator (< instead of >) or one comparator call. The same loop invariant holds; replace “sorted in ascending order” with whatever ordering you defined. Other DSA-style follow-ups (e.g., the string-palindrome problem) use the same shift-and-compare reasoning on different data.

The next stretch of placement questions on this algorithm tends to be: count the inversions in [8, 4, 2, 1] (answer: 6, because every pair is out of order); show why insertion sort is O(n + d) where d is the number of inversions; trace what happens if you replace the inner while with a binary-search-then-shift (the comparisons drop to O(n log n) but the shifts stay O(n^2), so the asymptotic time is unchanged). All three are worth doing on paper before the assessment.

A practical close: writing a sort and reasoning about its complexity is the floor of a placement coding round, not the ceiling. The companies that hired the most engineering freshers in FY26 increasingly ask one round about prompting and evaluating an LLM, on top of the standard DSA round. If you already have insertion sort and Big-O reasoning down, TinkerLLM is the lowest-friction way to add the second skill. It’s a self-paced LLM playground at ₹299 (launch) / ₹499 (regular), built for engineering students who have the algorithms half down and want to add the model-programming half before their next interview.