Title: Sorting in the "Restore" Model 

Speaker: Timothy Chan, University of Waterloo and HKUST

Time/Date: Friday, Feb 14, 11-12
Location: Room 3501

Abstract:

We consider the classical sorting problem in a model where the initial permutation
of the input has to be restored after completing the computation.  This model is
more restrictive than a traditional in-place algorithm model but more relaxed than
the read-only memory model.  We present a space-efficient algorithm in this "restore"
model that can sort n integers in O(n log n) time using only O(log n) words of
extra space.  Other related results are discussed.

(Joint work with Ian Munro and Venkatesh Raman, from SODA 2014.)