Is it conceivable that we will ever bypass the lower bound of O(N lg N) for sorting?

Question

Do you think someone may eventually create a logical "short circuit" technique that reduces the lower bound?

( I believe I am understanding the concept correctly, please correct me if I am inaccurate )

Answer 1

We already have. In the special case where the items to be sorted fall into a range which is small compared to the number of items to sort, we can use a pigeonhole sort, which runs in O(n) time. In the more general case, we can use radix sort, which runs in O(n·k) time, where k is the length, in bits, of the items to be sorted (whether this is faster than O(n·lg n) depends on the items to be sorted). You can find out more at the wikipedia links below.

Answer 2

Its starting to seem less and less likely. We've been stuck at O(N lg N) for a long time now. In the early days, new sorting algorithms were created quickly, each better than the last. I can't remember the last new algorithm that was created, so it seems like a pretty good bet, with the current technology, it won't be getting much better.

Answer 3

i vaguely remember a seminar in grad school where they said they achieved O(N log (log N))

i'll look at my old notes to see if i can dig up a reference