[cs631apue] Sorting working on Linux, but not Unix

[Jan Schaumann]

Jason Ajmo <jajmo at stevens.edu> wrote:
> After lots of reading, printing, and testing, I have finally found the
> bug.
> 
> In my sort function, instead of returning s1->st_size > s2->st_size, I
> had to return return s1->st_size - s2->st_size.

Glad you found the bug!

Per the fts(3) manual page, the compar function

"should return a negative value, zero, or a positive value to indicate
if the file referenced by its first argument comes before, in any order
with respect to, or after, the file referenced by its second argument."

So returning "x > y" wasn't right, since that can only ever return
either 0 or 1, meaning either "these two are equal" or "the first is
greater".  If the first file's size is smaller than the second file's,
then your implementation says basically "sort these two the same".

> I have absolutely no idea why this was working on Linux and not
> NetBSD.

Not sure.  I suspect it's a difference in the qsort(3) implementation.
Different approaches (recursive vs non-recursive, placement of 'equal'
elements relative to the pibot) could lead to the difference in sorting
output if the comparison function never returns "the first one is
smaller".  The data you're feeding quicksort here consists of elements
that are either "equal" or "larger" (never "smaller").  Since the
algorithm allows you to place "equal" elements on either side of the
pivot, it's possible that you end up with a properly sorted output (if
you happen to place them consistently before the pivot) or a not-sorted
output.

Compare
http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/stdlib/qsort.c?rev=HEAD
vs qsort.c in e.g. http://ftp.gnu.org/gnu/glibc/glibc-2.26.tar.xz to
confirm.  (Like any lazy instructor, I will leave this as an exercise to
you.)

-Jan