Insertion sort

Easy TimeO(n²) SpaceO(1)

Given an array arr of numbers, sort it into ascending order in place by taking each value in turn and putting it where it belongs among the values already sorted to its left. After every step that left-hand part is sorted and one longer, and a value already in the right place does not move at all.

Examples

Example 1

Input
arr = [5, 2, 8, 1, 4]
Output
[1,2,4,5,8]
The same five values, ascending.

Example 2

Input
arr = [1, 2, 3, 0]
Output
[0,1,2,3]
The 0 belongs at the front, and the three values above it each shift one place right.

The Code

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}
insertionSort([5, 2, 8, 1, 4]);
Done
Step through insertionSort([5, 2, 8, 1, 4]) call by call

More like this

All sorting examples (8) →