What is the compression impact on Sorted vs Unsorted list Given an unsorted list of objects with a compression ratio. Can you predict the impact on the ratio, if that list would have been sorted before compression?
Is there a reason to assume that sorting a list before compressing it will yield a better comparison ratio?
I know that I did not mention the compression algorithm, please address it in your answer.
 A: There are $x^n$ possible lists of $n$ objects, where there are $x$ different possible objects. So on average, over all possible such lists, a (non-lossy, optimal) compression algorith will give a file of size $n\log_2 x$ bits.
Of course, many decent algorithms will either know which objects are common in general, and make those take less space, or have an overhead stating which objects were common in this specific list, and make those take less space. So the uncommon lists will in that case actually take up more space after compression. But $n\log_2 x$ is the best guess for a "general" size for an arbitrary list.
Now presume we know that the list is sorted. Then there are only $\binom{x+n}{n}$ different possible lists. This is quite a lot smaller. How much smaller? If $x\gg n$ (i.e. most lists have only distinct objects), it's basically $\frac{x^n}{n!}$. This is a best case. The number of bits required on average to store a compressed list is for the best case $$n\log_2x-\log_2(n!)\approx n\log_2 x-n\log_2n+\frac{n}{\ln2}$$using Stirling's approximation.
