loading page

Hybrid Quicksort for Referenced Items with 1 and 3 pivots
  • Dennis de Champeaux
Dennis de Champeaux
Silicon Valley

Corresponding Author:[email protected]

Author Profile

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.