Quicksort vs. Shell

[Claudio L.]

I implemented all 3 methods for testing, since the answer wasn't clear after all the discussions.
I tested by sorting the same lists with 2, 4, 6, ... 1998 elements (tested on the PC, I might test on calc later just to get a feeling for the real timings). In the tests, I added significant overhead to the comparison, to make it similar to our use case.

Results were:

Fully random case:
Binary insertion: 2.01 sec
Shell sort: 2.12 sec
Quicksort: 1.83 sec

Reversed list:
Binary insertion: 0.56 sec
Shell sort: 1.67 sec
Quicksort: 2.28 sec

90% sorted, 10% random:
Binary insertion: 1.91 sec
Shell sort: 2.02 sec
Quicksort: 2.17 sec

So in the end, binary sort beats shell sort (point for Werner, good call there).
The fully random test is a best-case for quicksort, but it only outruns binary insertion by 10%. Binary insertion shines on fully reversed lists, and both shell sort and binary sort can beat quicksort with almost sorted or reversed lists.

So in the end, I think binary insertion is the method we'll use, since it's consistently fast, versus a quicksort that can fall down.

For the record:
I tuned each algorithm as follows:

• Shell sort: Nothing that could be improved.
• Binary sort: Once the position is found, memory is moved as a block using memmove(), rather than moving item by item in a loop. This increased the speed by a small percent, since memmove may use optimized CPU instructions (it may use SIMD on x86, and on ARM it uses STM/LDM). Still need to investigate what's the ideal threshold to switch from item-by-item loop to a memmove call due to the overhead of making the call.
• Quicksort: Pivot: Tried using the center element and the median of 3. Didn't see any difference in speed on the cases I was evaluating. In the end I left the median of 3.
  Recursion: Non-recursive with a local stack for up to 2^32 elements.
  Fall-back: For small lists falls back to plain insertion, I tuned the threshold until I found optimum value, which was between 6 and 8.
  

EDIT: Sort was made stable for all methods using method described in a post above.

Claudio