This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles 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.
This is an interesting algorithm. The algorithm summary box states the best case running time is O(1), in fact all the running times seem to be out by a factor of n. Further down the page the best case is shown to be O(n) which sounds more reasonable! --Mrtimuk (talk) 10:16, 10 May 2011 (UTC)
The following discussion is an archived discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.
The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.
If keys are "well distributed" among the subarrays, sorting occurs in linear time, much faster than comparison-based sorting, which can do no better than .
If keys are in order, even insertion sort takes linear time, so comparison sorts can certainly do better than . What the intro should be explaining is that in the average case this algorithm takes linear time, while a linear-time average is impossible for comparison sort. QVVERTYVS (hm?) 12:57, 15 June 2014 (UTC)