Insertion Sort Algorithm
===============================================================================
1. Algorithm Summary
-------------------------------------------------------------------------------
Insertion Sort is a simple comparison-based sorting algorithm that builds the
final sorted array one element at a time. It iterates through the input array,
comparing each element with the elements before it and inserting it into its
correct position in the sorted subarray.
(a) Key Features --------------------------------------------------------------
- In-place, meaning it sorts the array by modifying the input array itself
without requiring additional space.
- Stable, meaning the relative order of equal elements is preserved in the
sorted output.
- Adaptive, meaning its performance can be improved if the input array is
already partially sorted.
2. Complexity Analysis
-------------------------------------------------------------------------------
(a) Time Complexity -----------------------------------------------------------
Best-case: **O(n)** when the input array is already sorted. In this case, only
one comparison is needed for each element.
Average-case and worst-case: **O(n^2)**, where n is the number of elements in
the input array. In the worst case, when the input array is in reverse order,
Insertion Sort requires maximum comparisons and swaps.
(b) Space Complexity ----------------------------------------------------------
In all cases, space complexity is **O(1)** because insertion sort is an
in-place sorting algorithm
4. Implementation
-------------------------------------------------------------------------------
We implement insertion sort as a fsm with the following states:
#insertion-sort(arr<[u8]:4>) => <[u8]:4> :=
├ `Compare(arr,ix)
├ `Insert(arr,ix)
├ `Shift(arr,ix,arr)
└ `Done(arr).
#insertion-sort(arr) -> `Compare(arr, 0)
-- Check if we have iterated through the entire array. If not, we move to
-- the Insertion state.
`Compare(arr, i)
├ i >= length(arr) -> `Done(arr)
└ * -> `Insert(arr, i)
-- Compare the element at index i with the preceding elements. If necessary,
-- we shift elements to make space for the current element.
`Insert([], i) -> `Compare([], i + 1)
`Insert([head, tail], i)
├ head > arr[i] -> `Shift([head, tail], i, head)
└ * -> `Compare([head, tail], i + 1)
-- Handles the shifting of elements to the right to insert the current
-- element into its correct position.
`Shift([head, tail], j, key)
├ (j == 0 | arr[j - 1] <= key) -> arr[j] = key -> `Compare([head, tail], j + 1)
└ * -> arr[j] = arr[j - 1] -> `Shift([head, tail], j - 1, key)
-- Output the sorted array.
`Done(arr) => arr.