Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!microsoft!alonzo
From: alonzo@microsoft.UUCP (Alonzo Gariepy)
Newsgroups: comp.sys.handhelds
Subject: Re: sorting on the 28s
Message-ID: <9389@microsoft.UUCP>
Date: 9 Dec 89 11:53:36 GMT
References: <2423@gmu90x.gmu.edu>
Reply-To: alonzo@microsoft.UUCP (Alonzo Gariepy)
Organization: Microsoft Corp., Redmond WA
Lines: 24

In article <2423@gmu90x.gmu.edu> peraino@gmu90x.gmu.edu (peraino) writes:
> 
> >Well, insertion sort is only better than bubble sort by a constant factor.
> >I'll try to write a sort routine that sorts 50 numbers in 30 seconds or so.
> >This should be possible. (I hope)
> 
> I don't suppose anyone besides myself grabbed the recursive
> quicksort that was posted here a while back?

Running that quicksort on a list of 50 random number (generated with
<< 1 50 START RAND NEXT 50 ->LIST >>) took 19.5 seconds.  Running it
a second time on the sorted result took 118 seconds, six times longer.  
That's quicksort for you.  

There are ways to minimize this effect as discussed in Sedgewick's 
"Algorithms", a really good book on all sorts of things.

It is considered a good idea to switch to insertion sorting at some point 
in a quicksort.  Knuth gives a good treatment of this calculation on page 
120 of "The Art of Computer Programming Vol. 3".  Typically, you would
use an insertion sort on sublists with less than 10 or 20 elements.

Alonzo Gariepy
alonzo@microsoft