title: What sorting techniques can I use when comparing elements is expensive?
body: <h2>Problem</h2>
  <p>I have an application where I want to sort an array <em>a</em> of elements <em>a<sub>0</sub>, a<sub>1</sub>,...,a<sub>n-1</sub></em>. I have a comparison function <em>cmp(i,j)</em> that compares elements <em>a<sub>i</sub></em> and <em>a<sub>j</sub></em> and a swap function <em>swap(i,j)</em>, that swaps elements <em>a<sub>i</sub></em> and <em>a<sub>j</sub></em> of the array. In the application, execution of the <em>cmp(i,j)</em> function might be extremely expensive, to the point where one execution of <em>cmp(i,j)</em> takes longer than any other steps in the sort (except for other <em>cmp(i,j)</em> calls, of course) together. You may think of <em>cmp(i,j)</em> as a rather lengthy IO operation.</p>
  <p>Please assume for the sake of this question that there is no way to make <em>cmp(i,j)</em> faster. Assume all optimizations that could possibly make <em>cmp(i,j)</em> faster have already been done.</p>
  <h2>Questions</h2>
  <ul>
  <li><p>Is there a sorting algorithm that minimizes the number of calls to <em>cmp(i,j)</em>?</p>
  </li>
  <li><p>It is possible in my application to write a predicate <em>expensive(i,j)</em> that is true iff a call to <em>cmp(i,j)</em> would take a long time. <em>expensive(i,j)</em> is cheap and <em>expensive(i,j) ∧ expensive(j,k) → expensive(i,k)</em> mostly holds in my current application. This is not guaranteed though.</p>
  <p>Would the existance of <em>expensive(i,j)</em> allow for a better algorithm that tries to avoid expensive comparing operations? If yes, can you point me to such an algorithm?</p>
  </li>
  <li><p>I'd like pointers to further material on this topic.</p>
  </li>
  </ul>
  <h2>Example</h2>
  <p>This is an example that is not entirely unlike the application I have.</p>
  <p>Consider a set of possibly large files. In this application the goal is to find duplicate files among them. This essentially boils down to sorting the files by some arbitrary criterium and then traversing them in order, outputting sequences of equal files that were encountered.</p>
  <p>Of course reader in large amounts of data is expensive, therefor one can, for instance, only read the first megabyte of each file and calculate a hash function on this data. If the files compare equal, so do the hashes, but the reverse may not hold. Two large file could only differ in one byte near the end.</p>
  <p>The implementation of <em>expensive(i,j)</em> in this case is simply a check whether the hashes are equal. If they are, an expensive deep comparison is neccessary.</p>