Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Linear O(N) sorting with Radix Sort (2000)

codercorner.com

Post reply on HN
Print view View original

21–29 of 29 posts

Re: Linear O(N) sorting with Radix Sort (2000)

#21

Post by kevincox »

oriolid wrote: post #20
kevincox wrote: post #12

Earlier quoted context omitted.

Exactly. Radix sort isn't really linear. It is O(N * M) where N is the size of the collection and M is the number of possible items in the collection. If the number of possible items is fixed (like fixed-size integers) then it is effectively linear. However you can do this with strings just the same way.

Why M? The whole point of radix sort is to do the comparisons binary digit by digit so that the total number becomes O(N * log(M)).

Oops, you are right. I was thinking the entropy/bits of the possibilities but accidentally wrote number.

Re: Linear O(N) sorting with Radix Sort (2000)

#22

Post by [deleted] »

oriolid wrote: post #20
kevincox wrote: post #12

Earlier quoted context omitted.

Exactly. Radix sort isn't really linear. It is O(N * M) where N is the size of the collection and M is the number of possible items in the collection. If the number of possible items is fixed (like fixed-size integers) then it is effectively linear. However you can do this with strings just the same way.

Why M? The whole point of radix sort is to do the comparisons binary digit by digit so that the total number becomes O(N * log(M)).

[deleted]

Re: Linear O(N) sorting with Radix Sort (2000)

#24

Post by chasd00 »

OskarS wrote: post #19
colmvp wrote: post #3

> In every decent programmer’s toolbox lies a strange weapon called a Radix Sort. Where does it come from ? Who invented it ? I don’t know. Bit of a tangent, but at first this kind of caught me off guard because in this day and age it's easy to search for deeper info on established concepts and most articles would briefly have this answer (if the author cared to mention the history at all) but then I had to remind my…

An invaluable source for information like this (that did indeed exist in 2001) is The Art of Computer Programming by Donald Knuth. Knuth is extremely diligent in documenting the history of all algorithms he describes (arguably, TAoCP is the best source-book for the history of all computer science) and he has the following to say on the topic of Radix sort: > The sorting method just described is not immediately obviou…

i just looked TAoCP up on amz, the box set is $600. that's... pricey. sheesh

Re: Linear O(N) sorting with Radix Sort (2000)

#25

Post by actually_a_dog »

chasd00 wrote: post #24
OskarS wrote: post #19

Earlier quoted context omitted.

An invaluable source for information like this (that did indeed exist in 2001) is The Art of Computer Programming by Donald Knuth. Knuth is extremely diligent in documenting the history of all algorithms he describes (arguably, TAoCP is the best source-book for the history of all computer science) and he has the following to say on the topic of Radix sort: > The sorting method just described is not immediately obviou…

i just looked TAoCP up on amz, the box set is $600. that's... pricey. sheesh

I'm seeing used sets online for under $250. That seems well worth it to me, even if you only reference it once every couple years.

Re: Linear O(N) sorting with Radix Sort (2000)

#26

Post by Radim »

__s wrote: post #18
pfdietz wrote: post #16

Earlier quoted context omitted.

The model I usually consider is a RAM where the word size is ~ logn bits. This seems closest to real computers.

I find this article pretty insightful for thinking about algorithms that involve lots of memory: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

That article's discussion on HN (6 years ago!) was also quite interesting:

https://news.ycombinator.com/item?id=12383012

Re: Linear O(N) sorting with Radix Sort (2000)

#28

Post by bssrdf »

Radim wrote: post #9

There's C++ code included – great! But no actual timings :( I'd be curious to see a deeper discussion of practical run-times, in actual seconds, relative to other popular sorting algorithms. Especially if driven by a real task with well-motivated problem constraints. (As opposed to "1000 random integers!" micro-benchmarks, or "N goes to infinity" theoretical big-Ohs.) I personally find practical benchmarks the most e…

I implemented radix sort in cpython [0] and did some simple benchmarking comparing to python' built-in sort (Timsort I believe). It is indeed faster.

[0] https://github.com/bssrdf/RadixSortPy

Post reply on HN