I think Xichekolas had in mind adversarial techniques such as the one described in http://www.cs.dartmouth.edu/~doug/mdmspe.pdf. That paper assumes O(1) pivot selection.

I read the paper. Seems like they can not beat a median pivot (that takes O(k) to find at each step, but keeps the quicksort runtime of O(n log n).)

Still, a cool progam.

With random pivot selection, quicksort is expected O(n log n) time for all inputs. (The expectation is over the set of random numbers used to pick the random pivots, and doesn't involve the input at all). Algorithms like this are called "las-vegas".

Yes. And if your adversarial algorithm is good enough, it should work even in that case. (Of course any input is the worst case if all inputs have the same expected time.)

Wait if finding the median takes n time, and your sort takes n log n time then your best option is ~ n * log n * log n.

No, the O(n) for median selection is the same O(n) for set partition.

Ahh, ok, it takes N * log N to do the selection, but it's only O(l) for the length of the set partition each time. I was thinking it's the same n each cycle vs the same n at each depth. Err, nm it's hard to put into words.

PS: It still doubles the time but that's not important in O notation.

You can get away with less than the media. For example a pivot guaranteed to lie between the 25th and 75th percentile is good enough and can be found faster.

Personally, I really like merge sort. It makes few assumptions, it's stable, it works well with sorted inputs, can be split across multiple CPU's, and it works well with sequential input streams. Radix sort tends to be faster especially for strings, but it does not work for many data structures without adapting the algorithm. EX: Radix sorting doubles requires bit manipulation of the data.

Merge sort can be thought of as a kind of binary counting.

Doh, right, k select is the same problem. Median of medians is a good linear time technique, though.