Insertion sort

Insertion sort is a simple sorting algorithm that iterates over the slice moving back the elements larger than the previous ones, keeping the elements at the left of the current index ordered but not in their final position.

use super::AlgorithmState;

/// Sorts the slice using insertion sort algorithm and the comparison function `is_less` passed as
/// argument.
fn insertion_sort<T, F>(v: &mut [T], mut is_less: F)
where
    F: FnMut(&T, &T) -> bool,
{
    for i in 0..v.len() {
        let mut j = i;
        while j >= 1 && is_less(&v[j], &v[j - 1]) {
            v.swap(j, j - 1);
            j -= 1;
        }
    }
}

In terms of comparisons the algorithm performs $n-1$ in the best case (slice already sorted) and for the worst case (slice sorted in reverse order) each element must be compared with all the previous elements so the total number of comparisons can be summed up:

$$\sum _{i=1}^{n-1}i=\frac{(n-1)n}{2}$$

That simplifies to $O(n^2)$.

For exchanges, in the best case no exchanges are needed and in the worst case each insertion requires moving all the previous elements to the right this the total number of exchanges is similar to the number of comparisons in the worst case: $O(n^2)$.

Here is an animation of its execution:

The full source code can be found here