Insertion Sort

Insertion sort gradually builds a sorted array from an unsorted array.

1. Start with an unsorted array of \( n \) elements
2. Use splitIndex to partition the array into to partitions
   • All elements in positions less than splitIndex are sorted
   • All elements in positions greater than or equal to splitIndex have not been sorted
3. Take first value from yet-to-be-sorted partition and move it to the correct location in the sorted partition
   • Increment splitIndex
   • Sorted partition grows by one
   • Yet-to-be-sorted partition shrinks by one
4. Repeat until yet-to-be-sorted partition disappears

Best case performance

InsertionSort is fastest when no swaps are needed:

Here we have \( n \) iterations of the outer loop, so the algorithm is \( O(n) \).

Best case performance

InsertionSort is slowest when lots of swaps are needed:

Here we have \( n \) iterations of the outer loop and the inner loop runs once the first time, twice the second time, ... \( n \) times the last time. As a result, in the worst case, InsertionSort is \( O(n^2) \).