Extensions of Self-Improving Sorters

Siu-Wing Cheng, Kai Jin, Lie Yan

Ailon et al. (SICOMP 2011) proposed a self-improving sorter that tunes its performance to an unknown input distribution in a training phase. The input numbers $x_1,x_2,\dots ,x_n$…