All rights reserved.
%sccs.include.redist.man%
@(#)radixsort.3 5.4 (Berkeley) 11/21/90
#include <limits.h> #include <stdlib.h> radixsort(u_char **base, int nmemb, u_char *table, u_char endbyte);
The radixsort function sorts an array of nmemb pointers to byte strings, the initial member of which is referenced by base . The byte strings may contain any values; the end of each string is denoted by the user-specified value endbyte . The contents of the array are sorted in ascending order according to the ASCII order of the byte strings they reference.
Applications may specify a sort order by providing the table argument. If non-NULL, table must reference an array of UCHAR_MAX + 1 bytes which contains the sort weight of each possible byte value. The end-of-string byte must have a sort weight of 0. More than one byte may have the same sort weight. Table is useful for applications which wish to sort different characters equally; for example, providing a table with the same weights for A-Z as for a-z will result in a case-insensitive sort.
Radixsort is stable, that is, if two elements compare as equal, their order in the sorted array is unchanged.
Radixsort is a variant of most-significant-byte radix sorting; in particular, see D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. Radixsort takes linear time relative to the number of bytes in the strings.
Paige, R. [1987]. "Three Partition Refinement Algorithms", SIAM J. Comput. Vol. 16, No. 6.