Insertion Sort

Builds sorted array one element at a time by inserting into correct position.

Best: O(n) · Avg: O(n²) · Worst: O(n²) · Space: O(1)

48
49
88
56
35
97
35
88
32
11
41
62
75
22
63
Speed5
Size15
TypeScript
function insertionSort(arr: number[]): number[] {
  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;
}