Seminar: October 20

Janos Simon, University of Chicago

Sorting by Random Insertion

We analyze the number of comparisons made by the following randomized sorting algorithm: While the array is not sorted, choose a pair of elements and compare them. At each stage we choose uniformly at random among the pairs whose relationship was not determined by the previous stages. We obtain matching asymptotic upper and lower bounds. (Joint work with Mark Braverman.)