Sorting with expensive comparands
Dana Richards · International Journal of Computer Mathematics · 1984
Suppose each key, of an n element list to be sorted, has a price associated with it. The cost of a comparison is the sum of the prices and the cost of a computation is the total of the comparison costs. What sorting algorithm should we use so that the worst case cost is minimized. We present two approaches to form a census of all sorting algorithms that are optimal for some set of prices. We implemented these approaches and obtained limited results for small n. We also investigated other order statistics.