Quicksort vs. Shell

[Claudio L.]

(06-17-2014 05:12 PM)Marcus von Cube Wrote:  

(06-17-2014 03:03 PM)Claudio L. Wrote:  How did you manage the recursion part?

Our C stack is small (4K minus working memory) but the sort is limited to a maximum of 100 registers. If I'm not mistaken, the recursion cannot get deeper than ceil(log2(100))=7 levels.

Ideally, if you partition exactly in half every time, you get log2(N), but you don't know where your pivot falls within the list. If you have a list that's already sorted, and pick the last element as a pivot, for example, you get the worst case, where after each recursion, your partitions are not half the size, but merely (n-1) elements on one side and zero in the other, with 'n'= size of the previous partition.
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.
I'm thinking of using 4 kbytes of stack as well, but we have no plans to put a limit on the list size, so the possibility of stack overrun is always there.

Claudio