# Insertion Sort

## Dec. 29 2019

Insertion Sort is an in-place sorting algorithm that succeeds in sorting smaller arrays of values, but suffers with larger arrays. Insertion Sort has a linear (`O(n)`) best-case permormance, which makes it useful for adding additional items a sorted array that's already sorted.

## How it works?

When you want to sort an existing, unsorted array use Insertion Sort by traversing the array starting at index 0 (marked by `i`) and then selecting a pivot (`p = i + 1`). You then traverse backwards from the pivot (`p`) either until reaching index 0 or a value larger than the pivot, swapping adjacent values in the process.

## Implementation

``````def insertionSort(nums: list) -> list:
for i in range(len(nums) - 1):
p = i + 1  # pivot

while p > 0 and nums[p-1] > nums[p]:
nums[p-1], nums[p] = nums[p], nums[p-1]
p -= 1

return nums

print(insertionSort([5, 2, 3, 6, 1, 4]))
# => [1, 2, 3, 4, 5, 6]
``````

## Visual Representation ## Analysis

Insertion Sort works well for small datasets or when introducing new values into an already sorted array. It also benefits from being an in-place sorting algorithm, with minimal memory used.

``````Time:
Worst:   O(n^2)
Best:    O(n)   - when array is already sorted
Average: O(n^2)

Space: O(1) - swapping in place
``````