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.