Talk:Flashsort

Page started

This page was requested, so I wrote it. Any thoughts? I think it satisfies notability as independent publications from reputed scientists have cited and used it, in spite of the apparent fact that author is a terribly poor writer and has few academic credentials. Testing has shown that this algorithm is indeed the real deal. SamuelRiv 02:52, 6 November 2007 (UTC)

The worst case with Quicksort still is O(n^2).--Azrael60 (talk) 19:00, 29 November 2007 (UTC)

Of course, that's my fault. I will clarify the point. SamuelRiv 19:16, 30 November 2007 (UTC)

well i dont think so —Preceding unsigned comment added by 84.169.84.80 (talk) 16:32, 21 February 2008 (UTC)

Opening line

Flashsort is a sorting algorithm with extremely good O(n) efficiency for balanced data sets published in 1998 by Karl-Dietrich Neubert.

This made me laugh hard enough that I couldn't bring myself to change it. Such a specific sort! Xkcd (talk) 20:07, 28 June 2009 (UTC)

Algorithm

m needs to be defined explicitly. —Preceding unsigned comment added by 69.230.52.197 (talk) 00:42, 13 July 2009 (UTC)

I think m is the number of elements that need sorting. Am I wrong, or does this sort assume an even distribution of elements across the range of values? I can't see this sort working very well for even simple cases such as sorting surnames. --Surturz (talk) 19:42, 23 February 2010 (UTC)

Quicksort cannot be used to speed up the sort

AFAIK, quicksort has O(n log n) best case behaviour. Even if the list is perfectly sorted. Yet the article suggests using QuickSort instead of Insertion Sort (which has O(n) best case behaviour, giving Flashsort its inherent speed), which just doesn't make sense. Is this original (and poor) research? Or is there a variant of Quick Sort with O(n) best case behaviour that I'm not aware of? If no one corrects me in a week I'll remove the offending line.. Themania (talk) 10:08, 5 November 2009 (UTC)

Reading the citations, it looks like you can perform the search on just each class, where quicksort could be used without losing O(n). I feel the article needs to explain this, anyone want to change it? Themania (talk) 23:38, 5 November 2009 (UTC)

Just a reinvented bucket sort

It seems to me that Dr Neubert has just reinvented the in-place bucket sort. What he describes seems very similar to what is described in the abstract here: http://www.springerlink.com/content/31dvgnd8c911drka/

Furthermore, this page suggests that Dr Neubert used the same name as an older alogrithm:

http://www.itl.nist.gov/div897/sqg/dads/HTML/flashsort.html

Artelius (talk) 05:31, 6 July 2010 (UTC)

Specifically, the first pass of counting members of each class in an auxiliary vector L makes it look like an American flag sort. --Damian Yerrick (talk | stalk) 03:32, 29 December 2011 (UTC)

Yup, the algorithm described in Burnetas et al. (1997, submitted 1995) looks very similar. They call their algorithm Groupsort. Groupsort also uses only an additional vector, which stores starting positions of subarrays (buckets, groups) in the input-array. They claim that a size of 0.2n is optimal in practice (Neubert uses 0.42n). They sort the groups via Quicksort (Neubert sort his classes via Insertionsort). The approximate address computation looks very similar (they cite Isaac, Singleton, Sorting by Address Calculation, JACM, 1956 for the idea of using an approximate address computation).

--Gms (talk) 20:22, 24 February 2012 (UTC)

Implementations

There are not too many implementations found in the internet.

Should we cite implementations, for example in C, Ruby, Java, Scala...?--Bk1 168 (talk) 00:11, 19 March 2019 (UTC)