File RadixSort.h

↰ Parent directory (ADS/sort)

The sorts by the digits of the keys, beyond the book (which has Counting Sort and Pigeonhole Sort, the one-digit cases, in File CountingSort.h and File PigeonholeSort.h):

Definition (ADS/sort/RadixSort.h)

Detailed Description

  • radixSort() sorts integers and floating point numbers by their bytes, from the least significant (LSD), each pass a stable Counting Sort on one byte between the vector and a buffer: :math:` O( w ( n + 256 ) ) ` for keys of w bytes, no comparison. The key of a number is its bits made unsigned so that their order is the order of the numbers: the sign bit flipped for a signed integer, and for a floating point number all the bits flipped if it is negative and the sign bit otherwise (the order of IEEE 754, -0 before +0, the NaN at the ends). A first sweep finds the bytes in which some keys differ, and only those are counted (all the histograms in a second sweep) and make a pass, so that small keys in wide types cost only the bytes they use; when they differ in one byte alone, the key tells the number, and a counting sort writes the numbers back from one of each value, with no buffer. A vector larger than the cache (1 MiB), whose keys differ in 3 bytes or more, first goes by its top byte into the buffer, the one pass that scatters over the whole memory, and each part is sorted in the same way and then by the other bytes while it fits, so that their passes stay in the cache (an MSD pass before the LSD ones);

  • radixSortBy() is the same on any items, by an unsigned key that a function gives, stable, e.g., the records by one field;

  • americanFlagSort() is the radix sort from the most significant byte (MSD), in place: the items are permuted into their 256 buckets by following the cycles of the permutation, as the flag of the name divides into stripes, and each bucket is sorted recursively by the next byte, the small ones by insertion; O( n ) extra space for no buffer of the items, not stable;

  • msdRadixSort() sorts strings by their characters from the first one, the end of a string before every character: the first pass permutes them into their buckets in place, as the American flag sort does, and then each bucket has a buffer, made only if some bucket is not all of equal strings, between which and the vector the strings go back and forth, one move per pass, the character of each string read once per pass and kept aside, and the small groups sorted by insertion, so that it reads only the distinguishing prefixes of the strings: O( D + n log 256 ) for D the total length of those prefixes; the prefix that all the strings of a group share is first skipped by comparing them with one of them (one memcmp() for a string that keeps the whole prefix), so that a group of equal strings, or of strings with a long common prefix, costs one comparison instead of one pass per character;

  • bucketSort() sorts numbers in [ 0 , 1 ) into n buckets by their value, each sorted by insertion: O( n ) expected time on numbers drawn uniformly, :math:` O( n^2 ) ` in the worst case.

The contracts [see File Contract.h]: each sort ends with the same items sorted, an audit; bucketSort() needs numbers in [ 0 , 1 ). The functions are defined in RadixSort.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 12.3, https://algoritmicamente.it/materiali/libro/capitoli/cap12.pdf

    1. McIlroy, K. Bostic, M. D. McIlroy, Engineering radix sort, Computing Systems 6(1), 5-27, 1993

    1. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009, sections 8.3 and 8.4

  1. Herf, Radix tricks, 2001, http://stereopsis.com/radix.html (the key of a floating point number, the histograms in one sweep)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions