Quicksort vs. Shell

[Claudio L.]

(06-17-2014 05:22 AM)Paul Dale Wrote:  The 34S built in register sort command uses quick sort.
Comparisons are relatively very expensive so reducing the number of these is a win.
- Pauli

How did you manage the recursion part?

My main concern on using quicksort (besides the fact that it may be slower for some cases) is that it's recursive. Our C stack will be tiny and limited, so a recursive algorithm might never be able to work on larger sets (larger within the context of the calculator, with let's say 1000 elements). If the list is already sorted, standard quicksort will recurse a worst-case of 999 times (less if it's the median-of-3 version), needing about 16kbytes of RAM in the stack (assuming there's no local variables at all, just the return address saved and 3 arguments per call).
Another option would be to do the recursion in RPL, where we have all RAM for the stack to grow, but we'll take a big hit in performance.
There's non-recursive versions of quicksort, but they use temporary memory to operate as a simulated stack, so I don't see any advantage, unless you have a hardware-limited return stack like in the Saturn.

I found some performance benchmarks here, which were done for strings. Strings have slow comparison, so it is similar to our use case.
The comparison is old, so it doesn't use the best sequence for Shell sort (there should be a slight improvement), and also it's a 5000 elements and 10000 elements test, which is a bit too many for our target.
But it shows some trends: Shell sort seems to be the fastest of the insertion methods (better than binary insertion, as suggested by Werner). Shell is also one of the simplest to implement, that's why I chose it for this comparison.
The only other real contenders are heap sort and quick sort. Heap sort is more complex than shell sort, and about the same performance, so it's not worth the effort.
That leaves us with Quicksort vs Shell, hence the title of this thread.