[Solved]: What’s harder: Shuffling a sorted deck or sorting a shuffled one?

ignougroup
Problem Detail: You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits (a black box function taking no arguments and returning an independently uniformly random bit). Consider the following two tasks:

  1. The array is currently sorted. Produce a uniformly (or approximately uniformly) randomly selected permutation.
  2. The array consists of some permutation selected uniformly at random by nature. Produce a sorted array.

My question is

Which task requires more energy asymptotically?

I am unable to define the question more precisely because I don’t know enough about the connection between information theory, thermodynamics, or whatever else is needed to answer this question. However, I think the question can be made well-defined (and am hoping someone helps me with this in an answer!). Now, algorithmically, my intuition is that they are equal. Notice that every sort is a shuffle in reverse, and vice versa. Sorting requires $log n! approx n log n$ comparisons, while shuffling, since it picks a random permutation from $n!$ choices, requires $log n! approx n log n$ random bits. Both shuffling and sorting require about $n$ swaps. However, I feel like there should be an answer applying Landauer’s principle, which says that it requires energy to “erase” a bit. Intuitively, I think this means that sorting the array is more difficult, because it requires “erasing” $n log n$ bits of information, going from a low-energy, high-entropy ground state of disorder to a highly ordered one. But on the other hand, for any given computation, sorting just transforms one permutation to another one. Since I’m a complete non-expert here, I was hoping someone with a knowledge of the connection to physics could help “sort” this out! (The question didn’t get any answers on math.se, so I’m reposting it here. Hope that is ok.)

Asked By : usul

Answered By : Peter Shor

By Landauer’s principle, if you want to take a uniform random permutation of $n$ keys to a sorted one, and not keep any bits in the computer which reveal what the uniform random permutation was, you need to erase $log n! approx n log_2 n$ bits. This will take $(n ln n) k T$ energy. On the other hand, the computation taking the sorted array and $n log_2 n$ random bits to the random array is reversible, and thus the energy expended can be made arbitrarily small. Note that these are just theoretical lower bounds. The energy currently consumed by these processes on an actual digital computer bears no relation to the above analysis.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11299