Sorting and Selection with Random Costs

Stanislav Angelov, Keshav Kunal, Andrew McGregor

There is a growing body of work on sorting and selection in models other than the unit-cost comparison model. This work is the first treatment of a natural stochastic variant of th…