G²OAT seminar: The Hierarchy of Hereditary Sorting Operators


4. 12. 2023
13:00 – 14:00


Room TH:A-1247

Thákurova 7, Prague 6



Michal Opler from the Department of Theoretical Computer Science, FIT CTU, will speak at the regular Monday seminar of the G²OAT group. During his talk, he will discuss the hierarchy of hereditary sorting operators, examining how different classes impact the worst-case sorting time and identifying distinct categories.

Event website


We consider the following general model of a sorting procedure: we fix a hereditary permutation class C , 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 [ n ] = 1 , 2 , , n , i.e., a sequence where each element of [ n ] appears once. In every step, the sorting procedure picks a permutation σ of length n from C and rearranges the current permutation of numbers by composing it with σ . The goal is to transform the input π into the sorted sequence 1 , 2 , , n 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 C falls into one of five distinct categories. Disregarding trivial extreme cases, a worst-case sorting time of a hereditary class is either Θ ( n 2 ) , or a function between O ( n ) and Ω ( n ) , or O ( log 2 n ) , and for each of these cases, we provide a structural characterization of the corresponding hereditary classes.