Shell sort

Shell sort is an extension of insertion sort because it permits to exchange elements of the array that are far apart. It does it sorting elements at specific gaps which produces partially sorted slices that can be eventually sorted by insertion sort.

It works as follows:

1. Choose a sequence of gaps: This is the most difficult part of the Shellsort algorithm. Any sequence that contains 1 yields a correct sort because it makes the final pass an ordinary insertion sort.
2. Sort the gap sub arrays: Each element in the gap sequence generates a sub array of elements spaced by that gap value. This step sorts the sub array using insertion sort generating a partially sorted general array.
3. Repeat for smaller gaps: Continue the process with the rest of the elements of the gap sequence until the final pass which is a regular insertion sort with a gap of 1. At that stage the array is close to being sorted which is where the insertion sort is more efficient.

There has been proposed different gap sequences such as:

The implementation admits passing one of the previous sequences:

/// Sorts the slice using shell sort algorithm and the comparison function `is_less` passed as
/// argument. The decreasing interval sequence is also passed as argument.
fn shell_sort<T, F, S>(v: &mut [T], mut is_less: F, seq: S)
where
    F: FnMut(&T, &T) -> bool,
    S: Iterator<Item = usize>,
{
    for h in seq {
        let mut i = h;
        while i < v.len() {
            let mut j = i;
            while j >= h && is_less(&v[j], &v[j - h]) {
                v.swap(j, j - h);
                j -= h;
            }
            i += 1;
        }
    }
}

The average algorithm performance depends on the gap sequence used. Using the bench cli tool on a M1 processor executing 100 iterations the results obtained are as follows:

See the algorithm in action using the Knuth sequence:

The full source code can be found here