MV's blog

Insertion Sort

Insertion sort is an elementary sort that works by visiting each item in the array - starting from the first and comparing it to it's predecesors. If the predecesor is greater than the item, it swaps - inverts their places. It continues to do so until it finds an element which is less than the item.

Time complexity

To sort a randomly-ordered array with distinct keys, insertion sort uses~1/4 N2 compares and ~1/4 N2 exchanges on average.

Best case: if comparing to ascending order and the array is already sorted it makes N-1 compares and 0 exchanges.

Worst case: if the array is in descending order (and no duplicates) insertion sort makes ~1/2 N2 compares and ~1/2 N2 exchanges.

For a partially sorted array; an array where the numbers of inversions is <= c * N, i.e linear, insertion sort runs in linear time.

Sample typescript implementation for sorting numbers in ascending order.

function insertionSort(numbers: number[]): void {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i; j - 1 >= 0; j--) {
      if (numbers[j] < numbers[j - 1]) {
        // Swap them
        const tmp = numbers[j];
        numbers[j] = numbers[j - 1];
        numbers[j - 1] = tmp;
      } else {
        // All the elements on the left are less than
        // continue to the next item
        break;
      }
    }
  }
}