Premium
Engineering a sort function
Author(s) -
Bentley Jon L.,
McIlroy M. Douglas
Publication year - 1993
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380231105
Subject(s) - debugging , dijkstra's algorithm , sort , computer science , sorting , function (biology) , theoretical computer science , scheme (mathematics) , merge sort , programming language , sorting algorithm , parallel computing , mathematics , database , evolutionary biology , biology , graph , mathematical analysis , shortest path problem
We recount the history of a new qsortfunction for a C library. Our function is clearer, faster and more robust than existing sorts. It chooses partitioning elements by a new sampling scheme; it partitions by a novel solution to Dijkstra's Dutch National Flag problem; and it swaps efficiently. Its behavior was assessed with timing and debugging testbeds, and with a program to certify performance. The design techniques apply in domains beyond sorting.