AlgoView

Insertion Sort

Speed

About algorithm

Explanation

Insertion Sort builds the sorted array one element at a time by repeatedly taking the next element and inserting it into its correct position relative to the already sorted part.

Steps

  1. Start with the second element in the array.
  2. Compare it with elements before it and insert it into the correct position.
  3. Repeat for each element in the array.
  4. Shift elements as needed to make space for the insertion.
  5. Continue until the array is fully sorted.

Pseudocode

insertionSort(arr):
  for i from 1 to len(arr) - 1:
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
      arr[j + 1] = arr[j]
      j = j - 1
    arr[j + 1] = key

Complexity

Time: O(n²)

Space: O(1)