Quicksort’s elegant, 1960, bare bone version is extended to address the diversity of settings in which it is applied. We show that a best version for referenced types has worse performance than a best version for native types, and the other way around. Hence two versions developed around 1992 that can handle arrays with referenced as well as with native type elements are suboptimal. Different design choices are required. Using more than one pivot has been prototyped without follow up. We present several 3-pivot versions. We show also the results of parallel versions. The performance of these versions relies on novel designs: guaranteeing O(NlogN) worst case complexity with the Musser-defense minimizing recursive invocations or the number of comparisons, a novel technique to obtain high quality pivots that also supports linear complexity for constant array segments, using two gap array layouts in addition to single gap layouts, using an alternative to pairwise swapping for moving elements around, using more hybridization for members with specialized functionality, and using more layers than the traditional two.

This paper has multiple deliverables: the need for two different quicksort algorithms, the need for a hybrid with more than 2 design layers and at least 3 members, a new technique for obtaining pivots, a novel one pivot version extended with the Edelkamp enhancement and several three pivot versions. Each topic has its own section with a description of the underlying ideas and the benefits shown by performance results. Topic N+1 builds on top of topic N. All versions have O(NlogN) worst case complexity and linear complexity on constant inputs. Novel design elements are, among others: using the single element moving technique (in addition to pairwise swapping) and using array layouts with two gaps (in addition to single gap layouts). Given our focus on arrays with referenced items we assess our versions (in addition to timings) with comparison counts instead of with swap counts. We compare our versions favorably against quicksort versions we found in libraries and elsewhere.

Dijkstra’s Dutch Flag algorithm (DFA) can be used as a member of a quicksort hybrid to deal with, among others, a ‘difficult’ segment. We first show that the DFA can be wrapped so that this combination (with insertion sort and heapsort) is a ‘decent’ sorter. Subsequently we describe a different implementation of the DFA with a similar wrapper and compare their performance. Thirdly we show how these ‘mini’ sorters can be included in a five member hybrid quicksort sorter and we explain their contributions. The combination has NlogN worst case complexity and for constant input it has linear complexity. We compare several of these versions favorably against quicksort versions we found in libraries.