Insertion Sort

comparisonin-placestableadaptive

Press play to start

1function 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
12}

Step 1/0

Custom array:

Complexity

Best:O(n)
Average:O(n²)
Worst:O(n²)
Space:O(1)

Description

Builds the sorted array one element at a time by inserting each new element into its correct position within the already-sorted portion.

When to use

Excellent for small arrays or nearly-sorted data. Used as a subroutine in more complex algorithms like Timsort.