Can't be done faster than n * log2
n. How to? Read any article on sorting.
Whilst I agree that this is asking for the best possible sorting algorithm, the manner in which differing methods are compared is fairly uncommon: the cost of the algorithm is only the number of comparisons. In general, that's a very cheap part of the algorithm, and the memory usage, memory calls, function calls etc etc are the real issues.
Anyway, as is mentioned herehttp://en.wikipedia.org/wiki/Comparison ... ort_a_list
the lower bound must be at least ceiling(log2(n!)), but that bound isn't always realised - you can need 34 comparisons to sort 13 things but log2(13!) < 33. Its known that a thing called the Ford-Johnson algorithm does the best possible for small groups (apparently provably up to n = 47), but the interwob seems to think that its suboptimal. I haven't read that stuff so I can't say whether its actually true. I wouldn't be surprised if it were suboptimal, but I'm not going to vouch for a proof I haven't given a good look at.
Anyway, you can read about how Ford-Johnson works herehttp://www.google.com.au/url?sa=t&rct=j ... eg&cad=rja
I have no idea if that link will work for anyone but me. The article title is "A Variant of the Ford-Johnson Algorithm that is more Space Efficient" and the authors are Ayala-Rincón, Abreu, Siqueira (though I can't swear that that's the right accent on the o). Note though, that most articles on comparison sort don't mention Ford-Johnson.