Sorting Magazines and Boxes

Agata has $10$ magazines on her shelf. She wants to sort them according to her preferred order–for example, by issue number. Since magazines are thin, it is difficult to insert one between two others. Agata is therefore trying to devise a strategy that allows her to insert magazines only from the ends of the shelf.

Initially, Agata considers the following simple strategy:

“I pick the magazines from the shelf one by one and move them to a second shelf, inserting each magazine at the left end if it is smaller than the previous one, or at the right end otherwise.”

Once all magazines are moved, the first shelf becomes empty, allowing her to start a second round with the same strategy–inverting the roles of the two shelves–if the magazines are not yet sorted. This strategy is presented in the pseudocode below. Queue $M$ contains the magazines on the first shelf, and the double-ended queue (deque) $M^{\prime }$ represents the second shelf. We use standard queue operations: PopFront (removes and returns the first element), PushFront (inserts an element at the front), and PushBack (inserts an element at the back).

In theory, there is no difference between theory and practice; in practice, there is¹¹1This quote is often attributed to baseball player Yogi Berra.. When Agata considers how to implement her strategy concretely, she realizes that because the magazines are tall and thin, they cannot stand on their own. She would need an assistant to hold the magazines on one shelf while she manages the other.

The only other person home is her three-year-old son, Szymon, who is playing in the adjacent room. Agata must therefore improve her strategy. She realizes that because the shelves are in the corner of the room, the magazines are supported by the wall on the right end. Agata recalls reading that space can be used for multiple purposes simultaneously [4]. If she could eliminate the second shelf by reusing the space of the first shelf, she could support the magazines from the left end with one hand while using the other to pick and reinsert magazines.

After some thought, Agata arrives at a new realization of her strategy:

“I scan all the magazines from left to right. Each time I find a magazine $x$ that is smaller than the one immediately on its left, I mark $x$ (by pulling it slightly towards me). Once I have finished scanning, I take each marked magazine in the order it was marked and reinsert them at the left end of the shelf.”

This realization is equivalent to the first but significantly more convenient to perform manually. The following pseudocode illustrates this strategy using a single shelf $M$, implemented as a doubly-linked list with operations: Front (returns the first element), Next (returns the subsequent element), and MoveToFront (removes a given element from its current position and reinserts it at the front of the list). We utilize a queue $\mathrm{𝑀𝑎𝑟𝑘𝑒𝑑}$ to store pointers to the marked elements, allowing for $𝒪(1)$ reinsertion.

After ten rounds, Agata starts to wonder if this procedure will ever terminate. Is she simply repeating the same sequence of moves? However, the last three magazines are now in the correct order, which sounds promising… She decides to persevere, and finally, at the end of the 20th round, the magazines are completely sorted!

Agata wonders whether she was simply lucky this time, or if her strategy is guaranteed to work… Then she pauses: “Is this marking phase really necessary after all?” She devises a final improvement:

“I scan the magazines from left to right. Whenever I find a magazine $x$ smaller than the one on its left, I immediately pick $x$ and reinsert it at the left end.”

This refined strategy is illustrated in the pseudocode below. In this version, the move is performed immediately, eliminating the need for a marking queue. Note that when an element $y$ is moved to the front, the next element to be checked is compared against the same $x$ that was previously to the left of $y$.

“Well, this actually seems faster!” she thinks. Indeed, this time she finishes after only 6 rounds.

At this point, we are left with several questions: Do all of Agata’s strategies always converge to the sorted list? And if so, what is the number of rounds or steps in the worst and average cases?

In the meantime, in the adjacent room, Agata’s three-year-old son, Szymon, is playing with his favorite toy: a Montessori tower (see Figure 1).

The toy consists of ten cubic boxes of different sizes. After Szymon successfully builds the tower by stacking all the cubes in decreasing order of size, he enjoys toppling. Now the boxes lie scattered across the carpet. Szymon knows that each box has one missing face, which must serve as the bottom; therefore, to put the toy away, he must nest the boxes one inside another in the correct order.

Szymon employs a simple, intuitive algorithm: First, he selects a box he assumes will be the outermost. He then picks up another box with his right hand and attempts to place it inside the first. He continues this process as long as each subsequently selected box fits within the one immediately preceding it. If the box does not fit, Szymon repeatedly removes the innermost box with his left hand until the box currently in his right hand fits inside. The boxes removed from the partial stack are returned to the carpet in a disordered fashion. The specific order in which Szymon selects the remaining boxes is not immediately evident.

The following pseudocode illustrates the strategy. The partial order of boxes is implemented as a stack $S$, with the largest box at the bottom and the smallest at the top. The stack provides standard methods: Push (adds an element to the top), Pop (removes the top element), and Top (returns the top element). The collection $M$ of boxes remaining on the carpet supports the operations: Insert (returns a box to the collection) and RandomPick (selects a box based on Szymon’s undisclosed selection criterion).

Szymon is always able to order all the boxes within a few minutes, even though it is not immediately obvious to his parents that his algorithm is guaranteed to terminate. Moreover, the worst-case complexity of his approach may seem concerning. Was he simply lucky with the sequence of boxes he chose, or did he have some underlying intuition?

In Section 2, we analyze the complexity of Agata’s magazine sorting algorithms, while in Section 4 we examine the complexity of Szymon’s Montessori sorting algorithm. Finally, in Section 3, we discuss further potential improvements and experimental results.

Let us first analyze Agata’s algorithms. In full generality, let $n$ be the number of magazines to be sorted. For simplicity, we assume magazines are identified with their ranks $1,\mathrm{\dots },n$, though the algorithms only require a total strict order and do not assume a specific permutation of integers. We further assume all magazines are distinct.

As we have already mentioned, Naive Magazine Sort and Magazine Sort With Marking are essentially equivalent. Specifically, they perform the same number of rounds. Each round can be implemented in time linear in the number of magazines using appropriate pointer data structures: a queue and a double-ended queue for Naive Magazine Sort, and a list and a marking-queue for Magazine Sort With Marking. Thus, the crucial parameter in both algorithms is the number of rounds.

Let us analyze Magazine Sort With Marking. The algorithm consists of one or more rounds where magazines are scanned from left to right. In any given round, let $i$ be the largest element currently in a position smaller than $i$. It follows that element $i+k$ is in position $i+k$ for every $k>0$, and it will remain there after each subsequent round. In the next round, $i$ will be moved to position $i+j$ for some $j>0$, as there is at least one element to the right of $i$ that is smaller than its predecessor and will thus be moved to the front. This demonstrates that the algorithm converges in at most $n(n+1)/2$ rounds or $𝒪(n^3)$ total steps.

An almost-worst-case instance appears to be the permutation $(n,1,2,\mathrm{\dots },n-1)$. For this permutation, it takes exactly $n-1$ rounds for $n$ to reach the final position. After the $i$-th round, element $n$ is at position $i+1$, followed by $i+1,\mathrm{\dots },n-1$:

While the permutation $(n,1,2,\mathrm{\dots },n-1)$ seems to require $\omega (n)$ rounds, we have not yet proven this theoretically. Figure 2 contains a graph showing the number of steps the algorithm performed on permutations of this type.

Determining the exact complexity of Magazine Sort With Marking remains an open problem.

We now analyze the Magazine Sort No Marking algorithm. This variant performs at most $n-1$ rounds. To see this, let $i$ be the largest element not in the correct sorted position $i$ at the start of a round; specifically, suppose it is in position $i-j$ for some $j>0$. By the maximality of $i$, all elements to the right of $i$ up to position $i$ (i.e., those in position $i-j+1$ through $i$) must be smaller than $i$. Consequently, these elements will be moved to the front by the end of the current round. This guarantees that $i$ will occupy its correct position $i$ by the next round.

Thus, the algorithm requires at most $n-1$ rounds and is therefore worst-case quadratic ($𝒪(n^2)$ in the total number of element moves).

A worst-case instance for odd $n=2k-1$ is the permutation

This instance is constructed in such a way that before the $i$-th round, for $i=1,\mathrm{\dots },n-1$, the element $n+1-i$ is at the beginning, while all elements greater than $n+1-i$ (the $i-1$ largest elements) are already correctly placed at the end. This forces the algorithm to perform exactly $n-1$ rounds. For example:

A similar worst-case instance for even $n=2k$ is $(2k,2k-2,\mathrm{\dots },4,2,1,3,\mathrm{\dots },2k-1)$.

The implementation of the Magazine Sort With Marking algorithm can be improved so that in each round (except for the first), the total number of operations is proportional only to the number of moved elements. The core logic remains unchanged; intuitively, during the moving phase of the current round, we can simultaneously perform the marking for the next round.

Consider a round $i\ge 1$, and let $x$ be an element that is marked by the original Magazine Sort With Marking algorithm. This implies that its predecessor, $y=\text{Prev}(M,x)$, satisfies $y>x$. Now consider round $i-1$. Let $y^{\prime }$ denote $\text{Prev}(M,x)$ in round $i-1$. We have $y^{\prime }\ne y$, as otherwise $x$ would have been marked and moved in round $i-1$. This implies that either $y^{\prime }$ or $x$ was moved in round $i-1$.

In the optimized algorithm, whenever an element $u$ is removed from the list, we check if the subsequent element $v$ should be marked for the next round by comparing it with the predecessor of $u$. This corresponds to marking $v=x$ when $u=y^{\prime }$ is moved. Furthermore, whenever an element $u$ is prepended to the list, we check if the element $v$ that was previously at the front should be marked for the next round. This corresponds to marking $v=x$ when $u=y$ is moved to the front.

In the first round of Optimized Magazine Sort With Marking, the marking phase is exactly the same as in Magazine Sort With Marking. The list $\mathrm{𝑀𝑎𝑟𝑘𝑒𝑑}$ stores all the marked elements for the current round, and the list ${\mathrm{𝑀𝑎𝑟𝑘𝑒𝑑}}^{\prime }$ stores all the marked elements for the next round. We then iterate through all elements of the list $\mathrm{𝑀𝑎𝑟𝑘𝑒𝑑}$ and move them to the front one by one. Whenever a marked element is removed from the list $M$, we check if its successor in the list should be marked for the next phase; if so, we add it to ${\mathrm{𝑀𝑎𝑟𝑘𝑒𝑑}}^{\prime }$. Additionally, when the marked element is pushed to the front of the list $M$, we check if the previously first element of the list should be marked for the next round. In the end, ${\mathrm{𝑀𝑎𝑟𝑘𝑒𝑑}}^{\prime }$ becomes the new list $\mathrm{𝑀𝑎𝑟𝑘𝑒𝑑}$.

In Optimized Magazine Sort With Marking, there is no strict correspondence between the number of rounds and the total number of steps. The algorithm performs the same number of rounds as its predecessor, but each round is faster. This is confirmed by experimental analysis in Figure 3. The upper bound of $𝒪(n^3)$ steps still applies. As a comparison-based algorithm, the classic $\mathrm{\Omega }(n\log n)$ lower bound applies. The exact complexity, however, remains an open problem.

We can similarly optimize Magazine Sort No Marking by ensuring its complexity depends only on the number of magazines effectively moved. This requires reintroducing a focused marking strategy to track elements affected by displacements.

In the first round of Optimized Magazine Sort No Marking, the initialization is identical to the previous optimized algorithm. The list $\mathrm{𝑀𝑎𝑟𝑘𝑒𝑑}$ stores current marked elements, and ${\mathrm{𝑀𝑎𝑟𝑘𝑒𝑑}}^{\prime }$ stores the marked elements for the next round. When a marked element $x$ is processed, it is smaller than its predecessor $y=\text{Prev}(M,x)$. Therefore, $x$ and all elements to its right that are smaller than $y$ are moved to the front one by one. When an element is pushed to the front, it is removed from $\mathrm{𝑀𝑎𝑟𝑘𝑒𝑑}$ (if present), and we check if the previously first element of the list should be marked for the next round.

The optimized Magazine Sort No Marking maintains a worst-case complexity of $\mathrm{\Theta }(n^2)$. However, as shown in Figure 4, it performs significantly better than the basic version and Bubble Sort on random permutations.

A summary of the complexities of magazine sorting algorithms can be found in Table 1.

Let us now analyze Szymon’s algorithm in a general setting with $n$ boxes, of sizes $1$ (smallest) to $n$ (largest).

As established, the “partial order” of boxes stored in Montessori Tower Random Sort functions as a stack. At each step, a box is selected from the carpet; it is pushed onto the stack if its size is smaller than the box currently on top. Otherwise, boxes are popped from the stack one by one until the top box is larger than the box to be inserted.

First, we prove that the algorithm always terminates. The set of boxes stored on the stack can be represented as a binary sequence of length $n$ where the $i$-th bit is 1 if box $i$ is on the stack and 0 otherwise. Suppose box $j$ is selected from the carpet. The algorithm’s operations consist of zeroing all bits at positions $1,\mathrm{\dots },j-1$ (the pops) and setting the $j$-th bit to 1 (the push). If the sequence is viewed as a binary counter, where the $n$-bit is the most significant digit, then every step in the algorithm strictly increases the counter’s value. The counter starts at 0 (an empty stack) and reaches a maximum at $2^n-1$ (all boxes correctly nested). Since the counter strictly increases with each selection, the algorithm must terminate.

The binary counter argument shows there are at most $2^n$ distinct stack states. Unfortunately, a specific sequence of box selections can force the algorithm to visit every state. This occurs if we pick box $1$ every second step, box $2$ every second remaining step, and so on (see Figure 5).

If we measure complexity by unit operations on the stack, this behavior mirrors a binary counter counting from $0$ to $2^n-1$. It is well known that such a counter requires $\mathrm{\Theta }(2^n)$ bit-flips to reach the maximum value [2]. Since each bit-flip corresponds to a Push ($0\to 1$) or a Pop ($1\to 0$), the worst-case time complexity of Montessori Tower Random Sort is $\mathrm{\Theta }(2^n)$.

So how is it possible that Szymon consistently orders $n=10$ boxes within minutes? Assuming it takes a three-year-old $5$ seconds to move one box, the worst-case scenario would require $2\cdot 1024\cdot 5=10240$ seconds–nearly three hours!

The efficiency Szymon experiences lies in the expected-time analysis. If a box is selected uniformly at random from the collection $M$ at each step, then after an expected $n$ selections, the largest box ($n$) will be picked. Once box $n$ is pushed onto the stack, the stack is cleared of all smaller elements, and box $n$ becomes the permanent bottom of the stack. The problem then reduces to sorting the remaining $n-1$ boxes. Inductively, the total expected number of Push operations is: $n+(n-1)+\mathrm{\dots }+1=\frac{1}{2}{n}^2+\frac{1}{2}n$. The expected number of Pop operations is also $𝒪(n^2)$. Indeed, for $n=10$, with $5$ seconds per operation, the expected time is roughly $2\cdot 55\cdot 5=550$ seconds, or just over 9 minutes. This aligns perfectly with the observation that Szymon finishes “within a few minutes.”

This work shows that so-called intuitive sorting strategies admit rigorous mathematical analysis. We prove that Agata’s Magazine Sort No Marking is a physically realizable in-place sorting algorithm with worst-case running time $𝒪(n^2)$. In contrast, Szymon’s Montessori Tower Random Sort exhibits a pronounced separation between worst-case and expected behavior: while its worst-case complexity is exponential, $\mathrm{\Theta }(2^n)$, its expected running time is $𝒪(n^2)$.

For Magazine Sort With Marking, a key complexity question remains unresolved. We establish an $𝒪(n^3)$ upper bound and observe quadratic behavior in practice; however, determining whether the algorithm admits $\omega (n^2)$ rounds in the worst case remains open.