Talk:Proxmap sort

Time Complexity

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)

Move?

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 result of the move request was: not moved —Scott5114↗ [EXACT CHANGE ONLY] 23:49, 14 June 2011 (UTC)

---

Proxmap sort → ProxmapSort and ProxmapSearch – Relisted. Vegaswikian (talk) 18:25, 5 June 2011 (UTC)

• Standard spelling of algorithm, the one used by its inventor, is ProxMapSort; the article also discusses ProxmapSearch JacobsonUCI (talk) 18:36, 29 May 2011 (UTC)
• text styling not necessary.--Labattblueboy (talk) 19:56, 29 May 2011 (UTC)
• Wouldn't it be easier just to call it proxmap? 65.94.44.141 (talk) 04:57, 30 May 2011 (UTC)

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.

Comparison with comparison sort

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 $O(n\log n)$.

If keys are in order, even insertion sort takes linear time, so comparison sorts can certainly do better than $O(n\log n)$. 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)