Hacker News Reader

You can get another 2x speedup if you choose the pivot better. Right now it seems you're doing median of 3.

When you're doing Order Statistics (ie Selection/Quickselect) with 1M elements you should be very very close to the theoretical optimum (1.5N) for complexity. See my comment here:

https://news.ycombinator.com/item?id=6629117

If you're interested in choosing the best strategy.

HTH

View on HN

Neat! A quick skim of the referenced article in that comment (http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=6193457) shows that it solves a problem I'd wondered about for a while now, about how to optimally choose the pivots when computing order stats. (Yeah, I'm just doing median of 3 right now). If you want to sort the whole list, then clearly you want the pivots to be as near to the median as possible. But if you just want an order stat, then that's not necessarily true; if you wanted, say, the 10th percentile, my gut feeling would be that you should aim for your first pivot to be roughly the 20th percentile or so. I'll read that article more closely and see if I can improve even more.

Thanks, that's really helpful!

Reply on news.ycombinator.com