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

11–20 of 29 posts

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

#11

Post by vitorsr »

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…

The following repository implements radix sorting algorithms “from the ground up” and includes some benchmarks:

https://github.com/eloj/radix-sorting#cpp-benchmark

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

#12

Post by kevincox »

pfdietz wrote: post #5

Interestingly, radix sort can also lexicographically sort a collection of strings over a fixed alphabet in time O(sum of sizes of strings). It's not necessary to assume all the strings have the same length.

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.

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

#13

Post by __s »

kevincox wrote: post #12
pfdietz wrote: post #5

Interestingly, radix sort can also lexicographically sort a collection of strings over a fixed alphabet in time O(sum of sizes of strings). It's not necessary to assume all the strings have the same length.

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.

You can also say comparison sorts are O(N * ln N * M) where N is the size of the collection & M is the cost of comparison (eg string length for comparing strings)

But instead we say it requires O(N * ln N) comparisons

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

#15

Post by adrianN »

__s wrote: post #13
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.

You can also say comparison sorts are O(N * ln N * M) where N is the size of the collection & M is the cost of comparison (eg string length for comparing strings) But instead we say it requires O(N * ln N) comparisons

If you read the actual proofs, they count comparisons, not operations, when they arrive at O(nlogn). More advanced material analyses algorithms on random access machines with some fixed word size for cases where you can't assume that comparisons are constant time operations, or specialize for the data type, e.g. numbers, where you sometimes don't need o(n log n) comparisons at all (like with radix sort).

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

#16

Post by pfdietz »

adrianN wrote: post #15
__s wrote: post #13

Earlier quoted context omitted.

You can also say comparison sorts are O(N * ln N * M) where N is the size of the collection & M is the cost of comparison (eg string length for comparing strings) But instead we say it requires O(N * ln N) comparisons

If you read the actual proofs, they count comparisons, not operations, when they arrive at O(nlogn). More advanced material analyses algorithms on random access machines with some fixed word size for cases where you can't assume that comparisons are constant time operations, or specialize for the data type, e.g. numbers, where you sometimes don't need o(n log n) comparisons at all (like with radix sort).

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

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

#17

Post by ccalloway »

__s wrote: post #13
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.

You can also say comparison sorts are O(N * ln N * M) where N is the size of the collection & M is the cost of comparison (eg string length for comparing strings) But instead we say it requires O(N * ln N) comparisons

M = string length and M = number of different possible values are very, very different. One is the exponential of the other.

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

#18

Post by __s »

pfdietz wrote: post #16
adrianN wrote: post #15

Earlier quoted context omitted.

If you read the actual proofs, they count comparisons, not operations, when they arrive at O(nlogn). More advanced material analyses algorithms on random access machines with some fixed word size for cases where you can't assume that comparisons are constant time operations, or specialize for the data type, e.g. numbers, where you sometimes don't need o(n log n) comparisons at all (like with radix sort).

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

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

#19

Post by OskarS »

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 obvious, and it isn't clear who first discovered the fact that it works so conveniently. A 19-page pamphlet entitled "The Inventory Simplified," published by the Tabulating Machines Company division of IBM in 1923, presented an interesting Digit Plan method for forming sums of products in their Electric Sorting Machine ... This punched-card tabulating method leads naturally to the discovery of least-significant-digit-first radix sorting, so it probably became known to the machine operators. The first published reference to this principle for sorting appears in L. J. Comrie's early discussion of punched-card equipent [Transactions of the Office Machinery Users' Assoc., Ltd (1929)]

> ...most people rejected the idea of radix sorting within a computer, until H.H. Seward['s master thesis in 1954] pointed out that... []

Presumably, this is a method that has been discovered and rediscovered many times by many programmers and punch-card operators, but that H. H. Seward made it practical for digital computers in 1954.

PS. TAoCP is awesome. Even if you can't follow the more advanced math, just having this book on the shelf to look up stuff like this is lovely if you do this kind of thing professionally. Knuth is just a fantastic scholar and teacher. Just flipping through the things is a joy.

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

#20

Post by oriolid »

kevincox wrote: post #12
pfdietz wrote: post #5

Interestingly, radix sort can also lexicographically sort a collection of strings over a fixed alphabet in time O(sum of sizes of strings). It's not necessary to assume all the strings have the same length.

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)).
Post reply on HN