Quicksort vs. Shell

[Claudio L.]

(06-17-2014 06:51 PM)Werner Wrote:  

(06-17-2014 06:07 PM)Claudio L. Wrote:  So log2(N) is a best-case scenario, N-1 is the worst-case, and in reality it's somewhere in between. Even with more advanced pivot picking techniques, there's always the chance that a wickedly-sorted list makes you hit the worst case.
If you sort 100 registers, and happen to hit the worst case, you'll need 99*sizeof(int)*(1+3) (assuming 1 for return address, and 3 arguments, but your implementation could have just 2 arguments), which is less than 1600 bytes. Your 4 kbytes of stack should be plenty.

Claudio

At every step you split the set in two halves, and if you sort the smaller half first you'll need at most log2(N) stack size.
Werner

Yes, I just read about that trick a few moments ago. It's also recommended not to recurse the second half, but do a tail call, so no stack is used. So it's not so bad after all, I can live with log2(N). I'll give it a shot.