3 ms·
For comparison-based sorts, no. There are some good links if you google "lower bound of comparison-based sorting algorithms". Knuth's question was a joking ref
by jey 19y ago
For comparison-based sorts, no. There are some good links if you google "lower bound of comparison-based sorting algorithms".
Knuth's question was a joking reference to http://xkcd.com/342/ http://xkcd.com/342/
- tocomment 19y agoThanks. The comic doesn't mention what the algorithm does. I thought I heard "search" in the lecture not sort.
- jey 19y agoOops, you're right, the 2nd-to-last panel is talking about A* and Dijkstra's search algorithms, but it's not clear what the last panel refers to. I just idiotically had assumed that the last panel was referring to sorting algorithms.