What type of study is this?

This is a Quantitative Study study (also classified as: Experimental Study).

September 29, 2025Open Access

Sorting permutations using a pop stack with a bypass

Key Points

The new sorting machine outperforms traditional algorithms, indicating broader potential applications in computational theory.
Characterization of sortable permutations through forbidden patterns leads to insights about existing sorting complexities.
An algorithm computes preimages for permutations, revealing those with fewer preimages and enhancing understanding of their structure.
Discussion on a dual pop stack system suggests avenues for further exploration in sorting device efficiency.

Abstract

We introduce a new sorting device for permutations which makes use of a pop stack augmented with a bypass operation. This results in a sorting machine, which is more powerful than the usual Popstacksort algorithm and seems to have never been investigated previously. In the present paper, we give a characterization of sortable permutations in terms of forbidden patterns and reinterpret the resulting enumerating sequence using a class of restricted Motzkin paths. Moreover, we describe an algorithm to compute the set of all preimages of a given permutation, thanks to which we characterize permutations having a small number of preimages. Finally, we provide a full description of the preimages of principal classes of permutations, and we discuss the device consisting of two pop stacks in parallel, again with a bypass operation.

Sorting permutations using a pop stack with a bypass

Key Points

Abstract

Cite This Study