Abstract: We study the sorting problem in the dynamic data model from Anagostopolous, Kumar, Mahdian, and Upfal. In it the underlying order of elements being sorted is changing as the sorting algorithm performs comparisons. The optimality of an algorithm is judged by the distance between a list the algorithm maintains and the underlying order. We present a partial proof that insertion sort achieves the optimal distance between the maintained list and the underlying order.
Work done with: Juan Jose Besa Vial, Michael Goodrich, and Timothy Johnson