The Shell Sort

The Shell Sort is a variation of the Insertion Sort.
Start with a "gap" k equal to half the size of the list.
Perform Insertion Sorts on the interwoven sublists.
- {a₀, a_k, a_2k, ...}
- {a₁, a_{k + 1}, a_{2k + 1}, ...}
- {a₂, a_{k + 2}, a_{2k + 2}, ...}, and so on, through
- {a_{k − 1}, a_{2k − 1}, a_{3k − 1}, ...}.
Divide k by 2 and repeat the above.
Quit when k = 0.
The run time is of order n log n (with probability near 100%).
Example - ShellSort.cpp.

This page was last modified on Apr 23, 2001

URL: http://people.hsc.edu/faculty-staff/robbk/Coms262/Lectures/ShellSort.html