We consider the following general model of a sorting procedure: we fix a hereditary permutation class , which corresponds to the operations that the procedure is allowed to perform in a single step. The input of sorting is a permutation of the set , i.e., a sequence where each element of appears once. In every step, the sorting procedure picks a permutation of length from and rearranges the current permutation of numbers by composing it with . The goal is to transform the input into the sorted sequence in as few steps as possible.
This model of sorting captures not only classical sorting algorithms, like insertion sort or bubble sort but also sorting by series of devices, like stacks or parallel queues, as well as sorting by block operations commonly considered, e.g., in the context of genome rearrangement.
Our goal is to describe the possible asymptotic behaviour of the worst-case number of steps needed when sorting with a hereditary permutation class. As the main result, we show that any hereditary permutation class falls into one of five distinct categories. Disregarding trivial extreme cases, a worst-case sorting time of a hereditary class is either , or a function between and , or , and for each of these cases, we provide a structural characterization of the corresponding hereditary classes.