sort.
I realize it's commonly said that radixsort is n*k rather than n*log(n).
I've been making that case that in real life, frequently k==log(n).
Anyway, here's the comparison, with code and graph:
http://stromberg.dnsalias.org/~strombrg/sort-comparison/
It can be difficult to distinguish O(n
On 5/1/2012 1:25 AM, Dan Stromberg wrote:
Anyway, here's the comparison, with code and graph:
http://stromberg.dnsalias.org/~strombrg/sort-comparison/
(It's done in Pure python and Cython, with a little m4).
Interesting, BTW, that an unstable quicksort in Cython was approaching
timsort as a C
://stromberg.dnsalias.org/~strombrg/sort-comparison/
It can be difficult to distinguish O(n) from O(n log n) on a log-log
plot, so I don't think that graph makes your point very well.
Thank you for your comment.
Do you have a suggestion for a better type of graph - or other
linearity/nonlinearity
On Tue, May 1, 2012 at 10:51 AM, Terry Reedy tjre...@udel.edu wrote:
On 5/1/2012 1:25 AM, Dan Stromberg wrote:
Anyway, here's the comparison, with code and graph:
http://stromberg.dnsalias.org/**~strombrg/sort-comparison/http://stromberg.dnsalias.org/%7Estrombrg/sort-comparison/
(It's done
==log(n).
Anyway, here's the comparison, with code and graph:
http://stromberg.dnsalias.org/~strombrg/sort-comparison/
It can be difficult to distinguish O(n) from O(n log n) on a log-log
plot, so I don't think that graph makes your point very well.
Thank you for your comment.
Do you
that radixsort is n*k rather than
n*log(n).
I've been making that case that in real life, frequently k==log(n).
Anyway, here's the comparison, with code and graph:
http://stromberg.dnsalias.org/~strombrg/sort-comparison/
It can be difficult to distinguish O(n) from O(n log n) on a log-log
plot
).
I've been making that case that in real life, frequently k==log(n).
Anyway, here's the comparison, with code and graph:
http://stromberg.dnsalias.org/~strombrg/sort-comparison/
(It's done in Pure python and Cython, with a little m4).
Interesting, BTW, that an unstable quicksort in Cython
