Insertion Sort

Insertion Sort

Insertion Sort builds the sorted array one element at a time. Think of sorting a hand of playing cards: you pick up each card and insert it into the correct position among the cards you already hold.

How It Works

1. Start with the second element (index 1). The first element is trivially sorted.
2. Store the current element as key.
3. Shift all sorted elements that are greater than key one position to the right.
4. Insert key into the gap.
5. Move to the next element and repeat.

function insertionSort(arr) {
  const a = [...arr];
  for (let i = 1; i < a.length; i++) {
    const key = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
  return a;
}

Complexity

Insertion sort is excellent for nearly sorted arrays and small datasets. Many production sort implementations (like Timsort) use insertion sort for small subarrays.

Your Task

Implement insertionSort(arr) that returns a new array sorted in ascending order.