Andrei Asinowski ; Cyril Banderier ; Benjamin Hackl - Flip-sort and combinatorial aspects of pop-stack sorting

dmtcs:6196 - Discrete Mathematics & Theoretical Computer Science, April 30, 2021, vol. 22 no. 2, Permutation Patterns 2019
Flip-sort and combinatorial aspects of pop-stack sorting

Authors: Andrei Asinowski ; Cyril Banderier ; Benjamin Hackl

Flip-sort is a natural sorting procedure which raises fascinating combinatorial questions. It finds its roots in the seminal work of Knuth on stack-based sorting algorithms and leads to many links with permutation patterns. We present several structural, enumerative, and algorithmic results on permutations that need few (resp. many) iterations of this procedure to be sorted. In particular, we give the shape of the permutations after one iteration, and characterize several families of permutations related to the best and worst cases of flip-sort. En passant, we also give some links between pop-stack sorting, automata, and lattice paths, and introduce several tactics of bijective proofs which have their own interest.


Volume: vol. 22 no. 2, Permutation Patterns 2019
Section: Special issues
Published on: April 30, 2021
Submitted on: March 12, 2020
Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,05A05, 05A19, 05A15, 05A16


Share

Consultation statistics

This page has been seen 37 times.
This article's PDF has been downloaded 12 times.