loading page

Dutch Flag Algorithm 2.0 for Quicksort
  • Dennis de Champeaux
Dennis de Champeaux
San Jose State University

Corresponding Author:ddc2@ontooo.com

Author Profile

Abstract

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.
21 Mar 2023Submitted to Software: Practice and Experience
22 Mar 2023Assigned to Editor
22 Mar 2023Submission Checks Completed
30 Mar 2023Review(s) Completed, Editorial Evaluation Pending
11 Apr 2023Reviewer(s) Assigned
05 Jun 2023Editorial Decision: Revise Major