Proof: let's take it as granted log(n!) = O(n log n). It remains to show that log(n!) = Omega(n log n).
log(n!) = sum of log i for i from 1 to n
>= sum of log (n/2) for i from n/2 to n (dropping half the terms (all nonnegative) and under-approximating the rest; technically, we need to floor or ceil n/2, but it doesn't matter)
= (n/2) log (n/2)
= (n/2) (log n - log 2)
= (1/2) n log n - n log 2 / 2
Hopefully, I don't need to bother proving that c(n log n) + kn = Theta(n log n) for constants c and k. We've shown that log n! is Omega(n log n) and O(n log n), so we have log n! = Theta(n log n) by definition.
So, the root of this thread is wrong (and so is the parent). Furthermore, the fact that log(n!) is smaller than n log n by a constant is irrelevant when comparing log(n!) to Theta(n log n). What would not be meaningless is comparing formulae for the exact number of comparisons performed by different algorithms.
As the article mentions log( n! ) is the theoretical lower bound on the comparison sorting unstructured data. This is a neat little argument so I thought I'd share it with you. Given an unsorted list of data (of length n), sorting is equivalent the discovering the permutation that will return the elements to their correct order. Now there are a total of n! possible permutations that we need to sift through. Now each comparison can be thought of as a yes-no, since we've all played 20 questions, I assume we all have noticed that with m yes-no questions we can distinguish between 2^m possibilities. Thus we need 2^m = n! ie m = log2(n!). Giving us our bound.
... this same tripe was submitted to reddit, they haven't actually switched yet, this is just a random paste of the timsort.txt file that exists within the Python SVN repository.
Agreed. The link is solely a description of timsort and has nothing to do with Java. There is, however, a bug in Sun's tracker suggesting that timsort be used for java.util.Arrays.sort. That bug has a state of "Accepted," which to my naive understanding indicates that Sun has consented to implementing the change. But then again, I don't have any experience with Java bug triage stages.
A better title for the submission would be "Timsort - Python's pragmatic merge sort" or something along those lines.
TimSort is essentially merge sort plus optimizations. The major optimization is that it identifies already-sorted subsequences within the input, and sorts these "runs" plus some surrounding elements using a fast binary insertion sort. This means that for input that isn't completely random, it doesn't need to do as many comparisons as a pure mergesort. TimSort has also been tuned based on empirical testing on real-world data/hardware.
Academic work on subjects like sorting tends to focus more on things like big-O runtimes and less on implementation details that lead to reducing the various constants that big-O simplifies out, or that arise from real-world data patterns rather than totally randomized or idealized data.
(I had to think this through, so I thought posting it might help someone else.)