Shell Sort

Shell sort is an optimization of insertion sort that allows elements to move across the list more efficiently. Instead of comparing only adjacent elements, Shell sort compares elements that are far apart using a decreasing sequence of gaps. This reduces the number of shifts required, especially for elements that start far from their correct positions.

Although its exact performance depends on the chosen gap sequence, Shell sort performs significantly faster than basic quadratic algorithms like bubble sort or insertion sort for medium-sized datasets.

Example Walk-through

Let’s start with this array:

[12, 34, 54, 2, 3]

We’ll use Shell’s original gap sequence: n/2, n/4, ..., 1

With 5 elements, the gaps become:

Gap = 2  →  Gap = 1

Pass 1 - gap = 2

We treat elements separated by 2 positions as a group, applying insertion-sort logic to each.

Index 2 - value 54 Compare with 12 (index 0) → stays in place.

Index 3 - value 2 Compare with 34 → shift Compare with 12 → shift Insert 2 at index 0

Array becomes: [2, 34, 54, 12, 3]

Index 4 - value 3 Compare with 54, shift Compare with 2, stays Insert at index 2

Array becomes: [2, 34, 3, 12, 54]

Pass 2 - gap = 1

Now it becomes a normal insertion sort, but with the array already partially sorted.

Insertion sort pass: Final result: [2, 3, 12, 34, 54]

Using larger gaps early makes the final insertion sort phase efficient because the data is already close to sorted.

Rust Implementation

This is an idiomatic in-place Shell sort implementation using Shell's original gap sequence.

pub fn shell_sort(arr: &mut [i32]) {
    let mut gap = arr.len() / 2;

    while gap > 0 {
        for i in gap..arr.len() {
            let temp = arr[i];
            let mut j = i;

            // Perform a gapped insertion sort
            while j >= gap && arr[j - gap] > temp {
                arr[j] = arr[j - gap];
                j -= gap;
            }

            arr[j] = temp;
        }

        gap /= 2;
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_sorts() {
        let mut input = vec![12, 34, 54, 2, 3];
        shell_sort(&mut input);
        assert_eq!(input, vec![2, 3, 12, 34, 54]);
    }
}

Example Usage

fn main() {
    let mut values = vec![9, 8, 3, 7, 5, 6, 4, 1];
    shell_sort(&mut values);
    println!("{:?}", values); // [1, 3, 4, 5, 6, 7, 8, 9]
}

Time and Space Complexity

Shell sort’s performance depends heavily on the gap sequence. There is no single Big-O classification for all versions, but Shell’s original sequence has well-known bounds.

Note: Better gap sequences (e.g., Ciura’s sequence) achieve much better performance, often close to O(n log² n) or better.

Space Complexity

Playground Links

Rust - Shell Sort