Insertion Sort

Last updated Nov 8, 2022 Edit Source

Incremental approach

1. Iterate through the array and maintain a sorted array in-place, at the start of the array.
2. For every element, loop through the sorted array backwards. Compare and swap the elements until it is in the correct spot.
3. Repeat until the entire array has been iterated through.

Equal elements are not swapped in position. This means that Insertion Sort is .

Best Case

• Occurs when the array is already sorted
  • 1,2,3,4,5
• 1 Key comparison is still required at each iteration
• Total of $n-1$ comparisons

Observe that the time complexity is $O(n+I)$ where $I$ is the number of inversions. This also means that the time complexity to sort an array that is almost sorted i.e. small number of inversions, is linear.

Worst Case

• Occurs when the array is reversely sorted, $\theta(n^2)$ inversions
  • 5,4,3,2,1
• Each iteration requires iterating through the entire sorted array
• Total: $$1+2+…+(n-1)=\sum_{i=1}^{n-1}i=\frac{(n-1)n}{2} $$