**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
```

## Further Reading

Insertion Sort - Wikipedia article on **Insertion Sort**.