On Fri, 17 Dec 2010 03:05:02 +0000 Russel Winder <rus...@russel.org.uk> wrote:
> On Thu, 2010-12-16 at 20:36 -0600, Craig Black wrote: > > It was brought to my attention that the quick sort has a very bad worst > > case, so I implemented a simple fix for it. Now the worst case (completely > > ordered) is the best case, and it only slows down the general case by a > > small percentage. I thought to myself, "it can't be this easy to fix quick > > sort". Does anyone see a flaw in this simple fix? Performs much better > > than Phobos in completely random and completely sorted data. Perhaps there > > is another case where it doesn't do as well? > > Is there any reason to not just follow Bentley and McIlroy, > ``Engineering a Sort Function,'' SP&E 23(11), p.1249-1265, November > 1993. It is what the Java folk and the Go folk do for sorting arrays > (and slices in Go). The Java folk use a modified Merge Sort for sorting > collections. It's all to do with stability as well as algorithmic > complexity. > > Quicksort and Merge Sort is, however, a research industry so it will > undoubtedly be the case that there is significantly more work done in > the last 17 years. This is especially true for parallel sorting. A > library for D undoubtedly needs both a sequential and a parallel sort > function. The Go folk haven't tackled this yet, and I can#t see the C++ > and Java folk tackling it for the forseeable future even though it is > basically a necessity. > > I have no doubt that people on this list could easily contribute to the > research activity in this area, and perhaps that is what some would like > to do, but to tinker away at algorithms outside the context of all the > research work done on this seems like the fastest way to be treated as > amateur hackers. > What about TimSort? http://en.wikipedia.org/wiki/Timsort (Was also considered to replace QuickSort in Lua.) Denis -- -- -- -- -- -- -- vit esse estrany ☣ spir.wikidot.com