next up previous contents index Search
Next: Source Code Up: 0.3.6 Shellsort Previous: 0.3.6 Shellsort Analysis

Shellsort, like the Mergesort and Quicksort, among others, divides a data set into subsets, sorts the subsets, and then recombines these sorted subsets. A Shellsort's average performance is thought to be about n3/2. The exact complexity of this algorithm is still being debated and is far too advanced for this presentation. Suffice to say that for mid-sized data sets it performs nearly as well if not better than the faster (n log n) sorts.

Scott Gasch