Quicksort vs. Shell

[Werner]

(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