# Talk:Proxmap sort

WikiProject Computer science (Rated C-class, Low-importance)
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.
C  This article has been rated as C-Class on the project's quality scale.
Low  This article has been rated as Low-importance on the project's importance scale.
WikiProject Computing / Software / CompSci (Rated C-class, Low-importance)
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.
C  This article has been rated as C-Class on the project's quality scale.
Low  This article has been rated as Low-importance on the project's importance scale.

## 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 sortProxmapSort and ProxmapSearchRelisted. 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 ${\displaystyle O(n\log n)}$.

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