--- _SB/Libc/stdlib/FreeBSD/qsort.3 2004-11-25 11:38:42.000000000 -0800 +++ _SB/Libc/stdlib/FreeBSD/qsort.3.edit 2006-06-28 16:55:53.000000000 -0700 @@ -40,41 +40,44 @@ .Dt QSORT 3 .Os .Sh NAME -.Nm qsort , qsort_r , heapsort , mergesort +.Nm heapsort , +.Nm mergesort , +.Nm qsort , +.Nm qsort_r .Nd sort functions .Sh LIBRARY .Lb libc .Sh SYNOPSIS .In stdlib.h +.Ft int +.Fo heapsort +.Fa "void *base" +.Fa "size_t nel" +.Fa "size_t width" +.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]" +.Fc +.Ft int +.Fo mergesort +.Fa "void *base" +.Fa "size_t nel" +.Fa "size_t width" +.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]" +.Fc .Ft void .Fo qsort .Fa "void *base" -.Fa "size_t nmemb" -.Fa "size_t size" +.Fa "size_t nel" +.Fa "size_t width" .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]" .Fc .Ft void .Fo qsort_r .Fa "void *base" -.Fa "size_t nmemb" -.Fa "size_t size" +.Fa "size_t nel" +.Fa "size_t width" .Fa "void *thunk" .Fa "int \*[lp]*compar\*[rp]\*[lp]void *, const void *, const void *\*[rp]" .Fc -.Ft int -.Fo heapsort -.Fa "void *base" -.Fa "size_t nmemb" -.Fa "size_t size" -.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]" -.Fc -.Ft int -.Fo mergesort -.Fa "void *base" -.Fa "size_t nmemb" -.Fa "size_t size" -.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]" -.Fc .Sh DESCRIPTION The .Fn qsort @@ -84,7 +87,7 @@ function is a modified selection sort. The .Fn mergesort -function is a modified merge sort with exponential search +function is a modified merge sort with exponential search, intended for sorting data with pre-existing order. .Pp The @@ -92,18 +95,18 @@ and .Fn heapsort functions sort an array of -.Fa nmemb +.Fa nel objects, the initial member of which is pointed to by .Fa base . The size of each object is specified by -.Fa size . +.Fa width . The .Fn mergesort function behaves similarly, but .Em requires that -.Fa size +.Fa width be greater than .Dq "sizeof(void *) / 2" . .Pp @@ -139,7 +142,7 @@ .Fn heapsort are .Em not -stable, that is, if two members compare as equal, their order in +stable; that is, if two members compare as equal, their order in the sorted array is undefined. The .Fn mergesort @@ -183,8 +186,8 @@ The function .Fn mergesort requires additional memory of size -.Fa nmemb * -.Fa size +.Fa nel * +.Fa width bytes; it should be used only when space is not at a premium. The .Fn mergesort @@ -195,8 +198,8 @@ Normally, .Fn qsort is faster than -.Fn mergesort -is faster than +.Fn mergesort , +which is faster than .Fn heapsort . Memory availability and pre-existing order in the data can make this untrue. @@ -218,10 +221,10 @@ .Bl -tag -width Er .It Bq Er EINVAL The -.Fa size +.Fa width argument is zero, or, the -.Fa size +.Fa width argument to .Fn mergesort is less than