1.\" Copyright (c) 1990, 1991, 1993 2.\" The Regents of the University of California. All rights reserved. 3.\" 4.\" Redistribution and use in source and binary forms, with or without 5.\" modification, are permitted provided that the following conditions 6.\" are met: 7.\" 1. Redistributions of source code must retain the above copyright 8.\" notice, this list of conditions and the following disclaimer. 9.\" 2. Redistributions in binary form must reproduce the above copyright 10.\" notice, this list of conditions and the following disclaimer in the 11.\" documentation and/or other materials provided with the distribution. 12.\" 3. Neither the name of the University nor the names of its contributors 13.\" may be used to endorse or promote products derived from this software 14.\" without specific prior written permission. 15.\" 16.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 17.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 20.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26.\" SUCH DAMAGE. 27.\" 28.\" @(#)radixsort.3 8.2 (Berkeley) 1/27/94 29.\" $FreeBSD$ 30.\" 31.Dd January 27, 1994 32.Dt RADIXSORT 3 33.Os 34.Sh NAME 35.Nm radixsort , sradixsort 36.Nd radix sort 37.Sh LIBRARY 38.Lb libc 39.Sh SYNOPSIS 40.In limits.h 41.In stdlib.h 42.Ft int 43.Fn radixsort "const unsigned char **base" "int nmemb" "const unsigned char *table" "unsigned endbyte" 44.Ft int 45.Fn sradixsort "const unsigned char **base" "int nmemb" "const unsigned char *table" "unsigned endbyte" 46.Sh DESCRIPTION 47The 48.Fn radixsort 49and 50.Fn sradixsort 51functions 52are implementations of radix sort. 53.Pp 54These functions sort an array of pointers to byte strings, the initial 55member of which is referenced by 56.Fa base . 57The byte strings may contain any values; the end of each string 58is denoted by the user-specified value 59.Fa endbyte . 60.Pp 61Applications may specify a sort order by providing the 62.Fa table 63argument. 64If 65.Pf non- Dv NULL , 66.Fa table 67must reference an array of 68.Dv UCHAR_MAX 69+ 1 bytes which contains the sort 70weight of each possible byte value. 71The end-of-string byte must have a sort weight of 0 or 255 72(for sorting in reverse order). 73More than one byte may have the same sort weight. 74The 75.Fa table 76argument 77is useful for applications which wish to sort different characters 78equally, for example, providing a table with the same weights 79for A-Z as for a-z will result in a case-insensitive sort. 80If 81.Fa table 82is NULL, the contents of the array are sorted in ascending order 83according to the 84.Tn ASCII 85order of the byte strings they reference and 86.Fa endbyte 87has a sorting weight of 0. 88.Pp 89The 90.Fn sradixsort 91function is stable, that is, if two elements compare as equal, their 92order in the sorted array is unchanged. 93The 94.Fn sradixsort 95function uses additional memory sufficient to hold 96.Fa nmemb 97pointers. 98.Pp 99The 100.Fn radixsort 101function is not stable, but uses no additional memory. 102.Pp 103These functions are variants of most-significant-byte radix sorting; in 104particular, see 105.An "D.E. Knuth" Ns 's 106.%T "Algorithm R" 107and section 5.2.5, exercise 10. 108They take linear time relative to the number of bytes in the strings. 109.Sh RETURN VALUES 110.Rv -std radixsort 111.Sh ERRORS 112.Bl -tag -width Er 113.It Bq Er EINVAL 114The value of the 115.Fa endbyte 116element of 117.Fa table 118is not 0 or 255. 119.El 120.Pp 121Additionally, the 122.Fn sradixsort 123function 124may fail and set 125.Va errno 126for any of the errors specified for the library routine 127.Xr malloc 3 . 128.Sh SEE ALSO 129.Xr sort 1 , 130.Xr qsort 3 131.Pp 132.Rs 133.%A Knuth, D.E. 134.%D 1968 135.%B "The Art of Computer Programming" 136.%T "Sorting and Searching" 137.%V Vol. 3 138.%P pp. 170-178 139.Re 140.Rs 141.%A Paige, R. 142.%D 1987 143.%T "Three Partition Refinement Algorithms" 144.%J "SIAM J. Comput." 145.%V Vol. 16 146.%N No. 6 147.Re 148.Rs 149.%A McIlroy, P. 150.%D 1993 151.%B "Engineering Radix Sort" 152.%T "Computing Systems" 153.%V Vol. 6:1 154.%P pp. 5-27 155.Re 156.Sh HISTORY 157The 158.Fn radixsort 159function first appeared in 160.Bx 4.4 . 161