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

1–10 of 29 posts

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

#2

Post by wruza »

a radix is just a digit in a decimal number. For example the number «42» has two digits, or two radices, which are 4 and 2. In hexadecimal the radix is 8 bits wide. For example the hexadecimal number 0xAB has two radices, A and B

Possibly a typo, A and B are 4 bits wide each.

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

#3

Post by colmvp »

> 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 myself the post was created in 2000, before Wikipedia (Radix Sort was added to Wikipedia in 2001), explanatory YouTube videos, and tons of writeups made us into instant "experts" of every field.

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

#4

Post by contravariant »

Somehow the article posits you need to check if the list is already sorted to support multiple passes, but this version of radix sort is designed to be stable which is all you need.

And technically checking if the list is already sorted is mostly faster because of caching, in theory radix sort could read each byte exactly once.

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

#6

Post by saurik »

The bottom of this article links to an article by Michael Herf (of f.lux fame, but also having had developed Picassa) on his radix sort optimizations. I considered these two articles to be absolutely critical to my understanding of algorithms back 20 years ago, when I was finally transitioning to "more complex" development while working with/for Jake Cannell (who had worked under Herf and was paying close attention to Pierre). I came to believe that sorts that don't at least try to use don't use radix somewhere are somehow "missing the point" of algorithmic design.

A decade later, while working on Cydia--which has a complex problem of trying to provide efficient local operation of a federated "app store" on mobile devices, and was dealing with a need to sort tens of thousands of packages (and which had been very very slow with users getting increasingly angry at me refusing to centralized the service)--I ended up determining my biggest issue was the sorting process and turning to radix sort, using some experimentally-chosen offsets for radix passes, which I could use to "mostly sort" the data before switching to an insertion sort "fixup" pass (which could then use the fully-unicode-aware number-parsing magical comparator people are used to).

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

#7

Post by cb321 »

wruza wrote: post #2

a radix is just a digit in a decimal number. For example the number «42» has two digits, or two radices, which are 4 and 2. In hexadecimal the radix is 8 bits wide. For example the hexadecimal number 0xAB has two radices, A and B Possibly a typo, A and B are 4 bits wide each.

I would say the author is also confusing the words "digit" and "radix".

   From The Free On-line Dictionary of Computing (30 December 2018) [foldoc]:

   radix

        The ratio, R, between the weights of adjacent
       digits in {positional representation} of numbers.  The
       right-most digit has weight one, the digit to its left has
       weight R, the next R^2, R^3, etc.  The radix also determines
       the set of digits which is zero to R-1.  E.g. decimal (radix
       ten) uses 0-9 and each digit is worth ten times as much as you
       move left along the number.

       (2006-11-10)
Admittedly, "digit distribution sort" might be a more descriptive name for the algorithm.

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

#9

Post by Radim »

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 exciting. They also help me identify different niches for different algos (caching, locality, array sizes, parallelization…).

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

#10

Post by Ono-Sendai »

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…

Here are some perf measurements I made a while ago with a serial and a parallel radix sort: https://forwardscattering.org/post/34
Post reply on HN