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.
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]
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
Insertion Sort - Wikipedia article on Insertion Sort.