Shell sort is a sorting algorithm that is a generalization of insertion sort, with two observations:
The Shell sort is named after its inventor, Donald Shell, who published the algorithm in 1959. Some older textbooks and references call this the "Shell-Metzner" sort after Marlene Metzner Norton, but according to Metzner, "I had nothing to do with the sort, and my name should never have been attached to it."
The original implementation performs O(...
more
Shell sort is a sorting algorithm that is a generalization of insertion sort, with two observations:
The Shell sort is named after its inventor, Donald Shell, who published the algorithm in 1959. Some older textbooks and references call this the "Shell-Metzner" sort after Marlene Metzner Norton, but according to Metzner, "I had nothing to do with the sort, and my name should never have been attached to it."
The original implementation performs O(n) comparisons and exchanges in the worst case. A minor change given in V. Pratt's book improved the bound to O(n log n). This is worse than the optimal comparison sorts, which are O(n log n).
Shell sort improves insertion sort by comparing elements separated by a gap of several positions. This lets an element take "bigger steps" toward its expected position. Multiple passes over the data are taken with smaller and smaller gap sizes. The last step of Shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be...
less
