2019/10/08 by Cerbai, Giulio, Cioni, Lapo, Ferrari, Luca
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1910.03578
We introduce a sorting machine consisting of k+1 stacks in series: the first k stacks can only contain elements in decreasing order from top to bottom, while the last one has the opposite restriction. This device generalizes \citeSM, which studies the case k=1. Here we show that, for k=2, the set of sortable permutations is a class with infinite basis, by explicitly finding an antichain of minimal nonsortable permutations. This construction can easily be adapted to each k ≥ 3. Next we describe an optimal sorting algorithm, again for the case k=2. We then analyze two types of left-greedy sorting procedures, obtaining complete results in one case and only some partial results in the other one. We close the paper by discussing a few open questions.