An Optimal Algorithm for Sorting Pattern-Avoiding Sequences

Michal Opler

We present a deterministic comparison-based algorithm that sorts sequences avoiding a fixed permutation $\pi$ in linear time, even if $\pi$ is a priori unkown. Moreover, the dependence…