I've ran some tests and found that Shellsort runs much faster on ordered and reversed lists compared to random lists and almost ordered lists.

        Random Reverse Order AlmostOrder
  time    24      5      4        29

The problem that is confusing me is that Shellsort performs insertion sorts on lists separated by gaps, and insertion sort only runs very fast on ordered lists, not reversed lists.

So my question is why does Shellsort work well on ordered and reversed lists when it uses insertion sort and insertion sort doesn't work well on reversed lists?


migrated from cstheory.stackexchange.com May 18 '13 at 20:22

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 2
    $\begingroup$ Please describe your benchmark. What exactly did you measure? The number may not imply what you think they do. $\endgroup$ – Raphael May 19 '13 at 14:53
  • 4
    $\begingroup$ May well be due to branch prediction. $\endgroup$ – greybeard Mar 13 '15 at 10:17
  • $\begingroup$ Can you also post the code? Sometimes things like this are all about the specific algorithm at hand not just the benchmark. $\endgroup$ – Jake Sep 2 '16 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy