You have an array of length $n$ containing $n$ distinct elements. You have access to a comparator on the elements (a black-box function that takes $a$ and $b$ and returns true if $a < b$, false otherwise). You have access to an unlimited supply of random bits. Consider the following two tasks:
- The array is currently sorted. Your algorithm should produce a uniformly (or approximately uniformly) randomly selected permutation.
- The array consists of some permutation (uniformly chosen by nature). Your algorithm should sort the array.
My question is:
Which task requires more "energy" asymptotically?
I am unable to define the question more clearly because I don't know enough about the connection between information-theoretic entropy and energy required for a computer operation. So I was hoping that an answer could clarify this connection. But I can think of two approaches to answering the question.
First, an algorithmic one: A comparison-based sort requires $n \log n$ comparisons and about $n$ "swaps"; a random shuffle should require no comparisons and about $n$ swaps (I think). But how much energy do these operations require?
Second, an information-theoretic one (which I am hoping to see!). Sorting a shuffled deck seems to require destroying many bits of information (which is costly, right?) whereas shuffling a sorted deck requires simply transferring my incoming random bits into the deck. It seems like the shuffling algorithm is "cheating" by getting access to random bits; can we quantify this?