# What's harder: Shuffling a sorted deck or sorting a shuffled one?

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.)

• I haven't thought this through at all, so caveat lector. If we start with a sorted array, then use merge sort, but instead of comparing, we use the random bits to do the merging (so instead of returning true iff $a<b$ we return true iff the random bit is $1$). The base case where we have two arrays of size one produces the two possible arrays of size two with a uniform probability. I haven't gotten any further than that. – Luke Mathieson Apr 14 '13 at 5:20
• I think that in order to answer this question, you first need to define the relative costs of operation; how much does it cost to read data, write data, and generate/obtain a random number? – mitchus Apr 14 '13 at 7:49
• @mitchus: I am mainly curious about the physical limits if we assume "optimally efficient" computers. My rough understanding is that there is a physical lower bound on the amount of energy required to "erase" a bit of information, while other operations require much less energy. So I wonder if this intuition is correct and formalizable enough to yield an answer. – usul Apr 14 '13 at 7:57
• What do you mean by erasing a bit? Overwriting it? As far as I know computers don't usually erase anything (except for privacy reasons) but merely "forget" about it by de-allocating the associated memory region. But maybe I am not grasping the abstraction level correctly here :) – mitchus Apr 14 '13 at 8:17
• @Patrick87 Unfortunately, a uniform energy model is too far from the truth to use it; see Evaluating Algorithms according to their Energy Consumption by Fudeus née Bayer and Nebel (2009). – Raphael Apr 14 '13 at 16:07

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.
• @usul: in that case,you've still erased the bits, so the algorithm still takes $(n \ln n) kT$ energy. It's just that in this case, there is a better algorithm you could have used, if you had known which fixed permutation the input was. – Peter Shor Apr 24 '13 at 16:29