Insertion Sorting

Easy

Grow a sorted prefix, one card at a time

Problem

Sort the array using insertion sort: grow a sorted prefix, inserting each new element into its correct place.

In simple words

Like sorting cards in your hand: take the next card and slide it back to where it belongs.

The idea

Treat the front of the array as already sorted and take the next element, sliding it left past everything bigger until it lands in place. It is how people sort a hand of cards, and it is O(n) on data that is already nearly sorted, which is why it is the fastest choice for small or almost-ordered arrays.

The trick

Best case O(n) when the array is already sorted — no element has to move.
Worst and average case O(n²), in place and stable.
Real library sorts fall back to insertion sort for subarrays of ~16 elements.

←→stepspaceplay

1/21

Brute force

timeO(n²)spaceO(1)

O(n) on nearly-sorted input.

1// grow a sorted prefix, inserting each key into place2for (let i = 1; i < n; i++) {3  const key = a[i];4  let j = i - 1;5  while (j >= 0 && a[j] > key) {6    a[j + 1] = a[j];7    j--;8  }9  a[j + 1] = key;10}

Input

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

Memory

key: —
j: —

Output

result: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [12, 11, 13, 5, 6]
Output:: [5, 6, 11, 12, 13]
Explanation:: Insert each card into its sorted place.

Example 2

Input:: nums = [4, 3, 2, 1]
Output:: [1, 2, 3, 4]
Explanation:: Each element slides left into position.

Example 3

Input:: nums = [2, 1]
Output:: [1, 2]
Explanation:: One insertion sorts a pair.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.