Dutch Flag Algorithm 2.0 for Quicksort
Dennis de Champeaux · 2023
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.