# Insertion Sort

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

- Start with an unsorted array of \( n \) elements
- 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

- All elements in positions less than
- 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

- Increment
- 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) \).