On Sat, Dec 13, 2008 at 7:01 PM, Tim Chase wrote: > >> I've never seen an algorithm for sorting that's better than >> O(n log n) on average. Are there any? I can't even imagine >> how a sort could possibly be done in O(n) time, since that >> would require looking at
An incorrect assumption about how all sorting algorithms must work, apparently! > All the algorithms I've seen for sorting in less than O(n log n) > have required knowledge of your data-set's features. The O(n log > n) family of sorts involve comparisons, where this is the lower > bound. Using methods other than comparison for sorting is where > you jump to O(n) with your counting/radix/bucket sorts. This > usually involves knowing the upper/lower bounds of the data, the > number of items to be sorted, and/or the distribution within them. > > My copy of _Introduction to Algorithms_ (by Cormen, Leiserson, > and Rivest) has an entire chapter (#9) on "Sorting in linear > time" that introduces all three of the aforementioned algorithms > with sample pseudo-code implementations for each. Nice. I might have to get a copy of a real algorithms book, clearly my class books left me a bit short uninformed about sorting algorithms. :) ~Matt --~--~---------~--~----~------------~-------~--~----~ You received this message from the "vim_use" maillist. For more information, visit http://www.vim.org/maillist.php -~----------~----~----~----~------~----~------~--~---
