Quicksort vs. Shell

[Werner]

(06-17-2014 09:15 PM)Claudio L. Wrote:  Binary insertion is still a very good algorithm for small sets. Shell is just an improvement
Now you made me wonder: what would happen if we use binary insertion instead of plain insertion on each gap run? I can't find anybody investigating that, so it's probably a bad idea, but would be nice to know.

Straight insertion is best for small sets and almost ordered sets, and that's exactly what shell sort exploits: the gaps are large at the beginning, so you sort small subsets, and smaller at the end, but by then the sets are almost in order. Binary insertion will likely degrade shellsort's performance instead of improving it.

Werner