The entropy of a signal is the logarithm base 2 of the number of signals that you could possibly be trying to send. Because with perfect compression, that is how many bits you need to encode that many different signals.

Since not all lists are sorted, there are more lists of a given size than sorted lists.

1M (ordered) list of numbers < 10^8 requires 3.16MB of RAM(10^6*log_2(10^8) bits). The theoretical lower bound to store unordered numbers is 0.96MB(log_2(comb(10^8+10^6-1, 10^6)) bits. Basically calculating number of different possible types of lists, taking its log is the entropy. Both the lists [1, 2] and [2, 1] are same if we don't want the ordering information. In the second case we just need counts of number with property that count[0] + count[1]+...+count[10^8] = 10^6 as counts give perfect information for the sorted list.

Because it's easier to compress (compared to when its contents is in a random order).