# 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.)