# Talk:Flashsort

WikiProject Computing (Rated Stub-class)
This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Stub  This article has been rated as Stub-Class on the project's quality scale.
 This article has been automatically rated by a bot or other tool as Stub-Class because it uses a stub template. Please ensure the assessment is correct before removing the `|auto=` parameter.

## 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: