Re: Unix question

[James Youngman]

On Sun, Oct 02, 2005 at 08:07:07PM +0200, Yoav Namir, Adv wrote:
> Dear Sirs,
>  
> I am a computer science student, I am having a dispute with my lecturer
> regarding unix "sort -n"...
>  
> I contended that "sort" utilizes qsort (quicksort), was I right ?
>  
> SOS please help me.


This response will seem hostile.  It is not intended to be, but you
may mistake my intent - email is not a good medium for communicating
non-verbal things.

OK, first, what do you mean by "unix sort"?  There is no single
universal implementation of "sort".  There are many versions of Unix
and each has their own implementation.  You have asked on the
bug-coreutils mailing list, but the GNU system provides an
imeplementation of "sort" that is just one among several.  Since there
are several implementations, there are many algorithms in use. 

Second, there is no equivalence between the qsort() library function
and Quicksort.  The qsort() implementation can use any convenient
algorithm.  The system I am writing this on has an implementation of
qsort() that sometimes uses Quicksort, and sometimes doesn't,
depending on the size of the input.

Third, qsort(3) is just a library function and sort(1) is a program,
so the library function cannot be the whole of the answer.  How do you
think that sort(1) handles inputs that do not fit into virtual memory?

Fourth, why are you asking us?  You are a computer science student.
Why do you not just look at the code and figure out for yourself which
algorithm is being used?  This would be a good opportunity for you to
learn something, wouldn't you say?  In your (presumed) later life as a
software practitioner, you will often need to look at some code and
decide questions like

1. Can we make this faster without making it more complex or prone to
   defects?
2. Is this code maintainable?  Can we make it maintainable, or should we 
   throw it away?
3. Can we make this code more simple without making it much slower?
4. Can we make this code use up less space withough slowing it down by
   more than x%?
5. How does this code work anyway?

So go look at the code for sort on your system, and figure out how it
works.  To use an idiom from elsewhere on the 'net, I'm trying to help
you teach yourself to fish.

Regards,
James.