Sorter classes based mainly on CilkSort
Cilk:
Basic algorithm:
if array size is small, just use a sequential quicksort
Otherwise:
1. Break array in half.
2. For each half,
a. break the half in half (i.e., quarters),
b. sort the quarters
c. merge them together
3. merge together the two halves.
One reason for splitting in quarters is that this guarantees
that the final sort is in the main array, not the workspace
array. (workspace and main swap roles on each subsort step.)
Leaf-level sorts use a Sequential quicksort, that in turn uses
insertion sort if under threshold. Otherwise it uses median of
three to pick pivot, and loops rather than recurses along left
path.
It is sad but true that sort and merge performance are
sensitive enough to inner comparison overhead to warrant
creating 6 versions (not just 3) -- one each for natural
comparisons vs supplied comparators.