Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!clyde!uunet!snorkelwacker!mit-eddie!uw-beaver!uw-june!dylan
From: dylan@cs.washington.edu (Dylan McNamee)
Newsgroups: comp.sys.handhelds
Subject: Re: sorting on the 28s
Message-ID: <10063@june.cs.washington.edu>
Date: 5 Dec 89 17:07:35 GMT
References: <2423@gmu90x.gmu.edu>
Reply-To: dylan@june.cs.washington.edu (Dylan McNamee)
Organization: University of Washington, Computer Science, Seattle
Lines: 19

>>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.
>>Ge' Weijers, ge@cs.kun.nl
>     I don't suppose anyone besides myself grabbed the recursive
>quicksort that was posted here a while back?

I grabbed the quicksort that was posted here (and is also in the gmu
archives) and was very impressed.  It outperformed my implementation
of mergesort by a factor of 2.  (both are O(nlogn) sorts)  

The only thing wrong with it is that it chooses the first element of 
the list as the pivot, which puts an already sorted list in its worst 
case (n^2).  

All in all, though, it is the most compact sort I've seen, and it is
quite fast.

dylan
dylan@cs.washington.edu