Recursive Insertion Sort

Easy

Sort the first n-1, then insert the last

Problem

Insertion sort written recursively: sort the first n-1 elements, then insert the last element into place.

In simple words

Sort the first n-1 recursively, then insert the last element into place.

The idea

Assume the first n-1 elements are already sorted — that is the recursive call — and then slide the final element back into its place. It is the same algorithm as the iterative version with the outer loop replaced by recursion.

The trick

Base case: a single element is already sorted.
The recursion depth is n, so it uses O(n) stack — the iterative form does not.

←→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.