Preimages of sorting algorithms

A sorting algorithm is a procedure that takes an input sequence and, by suitably applying certain allowed operations, outputs a weakly increasing sequence whenever possible. An algorithm can be seen as a map from the set of possible inputs to the outputs, therefore we can study its preimages. The thesis is organized as follows. Chapter 2 introduces the notations and the preliminary notions. Chapter 3 focuses on the preimages of Queuesort, and is joint work with Luca Ferrari. We describe a procedure that, for any permutation $\pi$, computes the preimages of $\pi$ under Queuesort. Additionally, we prove some enumerative results concerning the number of preimages of any permutation of a specific form. Finally, we compute the number of permutations with a fixed number k of preimages, for small values of k. Chapter 4 is joint work with Luca Ferrari and Mathilde Bouvel, and focuses on Bubblesort, answering the same questions of the previous chapter, and more. We consider the preimage tree of Bubblesort, and we give an exhaustive description of its shape and the heights of its nodes. In Chapter 5, which is joint work with Luca Ferrari, we define two new sorting algorithms, Cons and Min, both of which use a popqueue to sort permutations. The two algorithms look similar, but their differencies arise when they are applied twice. Finally, we find the preimages of any permutation under Cons. In Chapter 6 we consider a container formed by two queues in series, with several possibilities for the allowed operations. For each case, we describe the permutations that can be sorted. Finally, in Chapter 7, which is joint work with Mathilde Bouvel and Benjamin Izart, we study the interval poset of permutations, a partially ordered set studied by Bridget Tenner. After giving the basic definitions, we describe a correspondence between interval posets and decomposition trees, which is then used to answer all the open questions of the original paper. Chapter 8 contains some hints for further work.