Re: Postman's Sort

Postman's sort

   The Postman's sort is a variant of bucket sort that takes advantage of
   a hierarchical structure of elements, typically described by a set of
   attributes. This is the algorithm used by letter-sorting machines in
   [1]post offices: mail is sorted first between domestic and
   international; then by state, province or territory; then by
   destination post office; then by 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. This is similar to a
   [2]radix sort that works "top down," or "most significant digit
   first."^[3][5]^[4][6]



   Sent: Wednesday, May 27, 2026 at 10:30 PM
   From: "Robert Ramey via Boost" <[email protected]>
   To: [email protected]
   Cc: "Robert Ramey" <[email protected]>
   Subject: [boost] Postman's Sort
   Since there's been a lot of messages regarding sorting here, I thought
   I
   may as well chime in with my own experience here: Google Postman's sort
   _______________________________________________
   Boost mailing list -- [email protected]
   To unsubscribe send an email to [email protected]
   [5]https://lists.boost.org/mailman3/lists/boost.lists.boost.org/
   Archived at:
   [6]https://lists.boost.org/archives/list/[email protected]/message/
   BUQLEYVFY3LL27HUK3242S5QLHI2QOPQ/

References

   1. https://en.wikipedia.org/wiki/Post_office
   2. https://en.wikipedia.org/wiki/Radix_sort
   3. https://en.wikipedia.org/wiki/Bucket_sort#cite_note-Black2011-5
   4. https://en.wikipedia.org/wiki/Bucket_sort#cite_note-Ramey1992-6
   5. https://lists.boost.org/mailman3/lists/boost.lists.boost.org/
   6. https://lists.boost.org/archives/list/[email protected]/message/BUQLEYVFY3LL27HUK3242S5QLHI2QOPQ/
_______________________________________________
Boost mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://lists.boost.org/mailman3/lists/boost.lists.boost.org/
Archived at: https://lists.boost.org/archives/list/[email protected]/message/U33EJTZX2T4FCV6NB5AJ5PWCJYV7XCPO/