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:
- The array is currently sorted. Produce a uniformly (or approximately uniformly) randomly selected permutation.
- 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.)