Abstract
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.