(algorithm)
Definition: An efficient, in-place variant of radix sort that distributes items into hundreds of buckets. The first step counts the number of items in each bucket, and the second step computes where each bucket will start in the array. The last step cyclically permutes items to their proper bucket. Since the buckets are in order in the array, there is no collection step. The name comes by analogy with the Dutch national flag problem in the last step: efficiently partition the array into many "stripes". Using some efficiency techniques, it is twice as fast as quicksort for large sets of strings.
See also histogram sort.
Note: This works especially well when sorting a byte at a time, using 256 buckets.
Author: PEB
The flag of the United States of America.
Peter M. McIlroy, Keith Bostic, and M. Douglas McIlroy, Engineering Radix Sort, Computing Systems, 6(1):5-27, 1993.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 2 December 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "American flag sort", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 December 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/americanFlagSort.html