Given a sequence of n numbers and k parallel First-in-First-Out (FIFO) queues, how close can one bring the sequence to sorted order? It is known that k queues suffice to sort the sequence if the Longest Decreasing Subsequence (LDS) of the input sequence is at most k. But, what if the number of queues is too small for sorting completely? <OrderedList> <ListItem> <ItemNumber>1.</ItemNumber> <ItemContent> We give a simple algorithm, based on Patience Sort, that reduces the LDS by <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$k - 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. We also show, that the algorithm is optimal, i.e., for any <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$L > 0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>L</mi> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> there exists a sequence of LDS L such that the LDS cannot be reduced below <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$L - k + 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>L</mi> <mo>-</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> with k queues. </ItemContent> </ListItem> <ListItem> <ItemNumber>2.</ItemNumber> <ItemContent> Merging two sorted queues is at the core of Merge Sort. In contrast, two sequences of LDS two cannot always be merged into a sequence of LDS two. We characterize when it is possible and give an algorithm to decide whether it is possible. Merging into a sequence of LDS three is always possible. </ItemContent> </ListItem> <ListItem> <ItemNumber>3.</ItemNumber> <ItemContent> A down-step in a sequence is an item immediately followed by a smaller item. We give an optimal algorithm for reducing the number of down-steps. The algorithm is online. </ItemContent> </ListItem> </OrderedList> Our research was inspired by an application in car manufacturing.

Improving order with queues

期刊论文
出版模式：

开放获取
发表日期：

2026年4月13日

查看全文

Andreas Karrenbauer,
Kurt Mehlhorn,
Pranabendu Misra,
Paolo Luigi Rinaldi,
Anna Twelsiek,
Alireza Haqi,
Siavash Rahimi Shateranloo

摘要

Given a sequence of n numbers and k parallel First-in-First-Out (FIFO) queues, how close can one bring the sequence to sorted order? It is known that k queues suffice to sort the sequence if the Longest Decreasing Subsequence (LDS) of the input sequence is at most k. But, what if the number of queues is too small for sorting completely? 1.

We give a simple algorithm, based on Patience Sort, that reduces the LDS by $k - 1$ $k - 1$ . We also show, that the algorithm is optimal, i.e., for any $L > 0$ $L > 0$ there exists a sequence of LDS L such that the LDS cannot be reduced below $L - k + 1$ $L - k + 1$ with k queues.

Merging two sorted queues is at the core of Merge Sort. In contrast, two sequences of LDS two cannot always be merged into a sequence of LDS two. We characterize when it is possible and give an algorithm to decide whether it is possible. Merging into a sequence of LDS three is always possible.

A down-step in a sequence is an item immediately followed by a smaller item. We give an optimal algorithm for reducing the number of down-steps. The algorithm is online.

Our research was inspired by an application in car manufacturing.