5 Oct 2012 sness   » (Journeyer)

Radix sort - Wikipedia, the free encyclopedia

Radix sort - Wikipedia, the free encyclopedia: "Radix sort's efficiency is O(k·n) for n keys which have k or fewer digits. Sometimes k is presented as a constant, which would make radix sort better (for sufficiently large n) than the best comparison-based sorting algorithms, which are all O(n·log(n)). However, in general k cannot be considered a constant. In particular, under the common (but sometimes implicit) assumption that all keys are distinct, then k must be at least of the order of log(n), however other sorting methods become O(log (n) * log (n) * n) under similar constraints as they also need to step through an ever increasing number of symbols to do the comparisons."


Syndicated 2012-10-05 17:55:00 from sness

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!