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. -- Russel. ============================================================================= Dr Russel Winder t: +44 20 7585 2200 voip: sip:[email protected] 41 Buckmaster Road m: +44 7770 465 077 xmpp: [email protected] London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
signature.asc
Description: This is a digitally signed message part
