Improving order with queues

Abstract 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? We give a simple algorithm, based on Patience Sort, that reduces the LDS by $$k - 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> . We also show, that the algorithm is optimal, i.e., for any $$L &gt; 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>L</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> there exists a sequence of LDS L such that the LDS cannot be reduced below $$L - k + 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>L</mml:mi> <mml:mo>-</mml:mo> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> 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.