Timeline for How again do certain sorting methods use $o(n \log n)$ time?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 13, 2014 at 21:40 | vote | accept | Vandermonde | ||
| Dec 13, 2014 at 21:23 | comment | added | Vandermonde | I liked all these views, and in some sense the one above this one is my favorite. Still I've decided to accept this one since it helped me diagnose the problem (I had thought of the allowable range being bounded but not quantitatively on the same footing as $n$, and radix-sort queries and comparisons are the same except how they really aren't). Thanks again for all your answers. | |
| Dec 13, 2014 at 9:23 | comment | added | Pseudonym♦ | If keys repeat, then comparison-based sorting can be more efficient, too. The theoretical complexity of comparison-based sorting is $O(nH)$ where $H$ is the zero-order entropy of the sort keys. If the keys are distinct, $H = \log n$, but if they are not, $H < \log n$. | |
| Dec 12, 2014 at 1:59 | history | answered | Yuval Filmus | CC BY-SA 3.0 |