(algorithm)
Definition: A highly engineered variant of top-down radix sort where attributes of the key are described so the algorithm can allocate buckets and distribute efficiently.
Generalization (I am a kind of ...)
top-down radix sort.
See also multikey Quicksort.
Note: This is the algorithm used by letter-sorting machines in the post office: first states, then post offices, then routes, etc. Since keys are not compared against each other, sorting time is O(cn), where c depends on the size of the key and number of buckets. You probably used a form of this if you sorted lots of papers alphabetically: you put each paper in its pile (or bucket), A's, B's, C's, D's, etc., then sort each pile.
This is similar to radix sort, but works "top down" or "most significant digit first" while radix sort works "bottom up" or "least significant digit first". Also this does not merge distributed items while radix sort does.
After Robert Ramey (ramey@rrsd.com)
Author: PEB
Robert Ramey, The Postman's Sort, C Users Journal, August 1992.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 20 June 2011.
HTML page formatted Wed Mar 13 12:42:46 2019.
Cite this as:
Paul E. Black, "postman's sort", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 20 June 2011. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/postmansort.html