# What does > mean in this TAOCP solution?

For our assignment we have to implement a solution given to one of the problems in The Art of Computer Programming by D.E. Knuth (Ex24; Chapter 5: Sorting; TAOCP, Vol3, 2nd).
However, I fail to understand the solution given in TAOCP.

Problem: Three million men with distinct names were laid end-to-end, reaching from New York to California. Each participant was given a slip of paper on which he wrote down his own name and the name of the person immediately west of him in the line. The man at the extreme western end of the line didn’t understand what to do, so he threw his paper away; the remaining 2,999,999 slips of paper were put in a huge basket and taken to the National Archives in Washington, D.C. Here the contents of the basket were shuffled completely and transferred to magnetic tapes.

At this point an information scientist observed that there was enough information on the tapes to reconstruct the list of people in their original order. And a computer scientist discovered a way to do the reconstruction with fewer than 1000 passes through the data tapes, using only sequential accessing of tapes and a small amount of random-access memory. How was this possible?

In other words, given the pairs $(x_i, x_{i+1})$ for $1 \le i < N$, in random order, where the $x_i$ are distinct, how can the sequence $x_1 x_2 \ldots x_N$ be obtained, restricting all operations to serial techniques, suitable for use on magnetic tapes. This is the problem of sorting into order when there is no easy way to to tell which of two given keys precedes the other.

Solution by Norman Hardy, c. 1967: Make another copy of the input file; sort one copy on the first components and the other on the second. Passing over these files in sequence now allows us to create a new file containing all pairs $(x_i, x_{i+2})$ for $1 \le i \le N-2$ and to identify $(n-1,x_{n-1})$. The pairs $(n-1, x_{n-1})$ and $(n,x_n)$ should be written on still another file.

The process continues inductively. Assume that file F contains all pairs $(x_i,x_{i+t})$ for $1 \le i \le n - t$, in random order, and that file $G$ contains all pairs $(i,x_i)$ for $n-t < i \le n$ in order of the second components. Let $H$ be a copy of file $F$, and sort $H$ by first components, $F$ by second. Now go through $F$, $G$, and $H$, creating two new files $F'$ and $G'$, as follows. If the current records of files $F$, $G$, $H$ are, respectively $(x,x')$, $(y,y')$, $(z,z')$, then:

1. If $x' = z$, output $(x,z')$ to $F'$ and advance files $F$ and $H$.

2. If $x' = y'$, output $(y-t, x)$ to $G'$ and advance files $F$ and $G$.

3. If $x' > y'$, advance file $G$.

4. If $x' > z$, advance file $H$.

When file $F$ is exhausted, sort $G'$ by second components and merge $G$ with it; then replace $t$ by $2t$, $F$ by $F'$, $G$ by $G'$. Thus $t$ takes the values $2$, $4$, $8$, $\ldots$; and for fixed $t$ we do $O(\log N)$ passes over the data to sort it. Hence the total number of passes is $O((\log N)^2)$. Eventually $t \ge N$, so $F$ is empty, then we simply sort $G$ on its first components.

So here is my question:

1. If $x' > y'$, advance file $G$.
2. If $x' > z$, advance file $H$.

What do the more than sign denote here? $x'$, $y'$, $z$ are strings, is it referring to string size?

• @Raphael Didn't try too hard: while the 1st edition is on the shelf as often as not, I didn't even think of possible discrepancies from the 2nd, which I don't have equally convenient access to. That said, I'd denote the quote slightly differently (Volume immediately following the title, TAoCP, Ans. to Ex. 24 in Ch. 5). The lines were out of sequence before the edit, in sequence (and numbered correctly) after. No "comparison operator glyph" is used in the problem statement, a simple > as shown in the solution sketched and attributed to N. Hardy. – greybeard Jan 26 '17 at 21:41
• @greybeard Oh, the two copies where in different order. I see, should have looked at the full diff. Never mind! Agree reg. the title; edited. – Raphael Jan 26 '17 at 22:12
• (@Raphael: the fun thing about Knuth's presentation is the order i) $\text{If } x' = z…F \text{ and } H \text{ ii) If } x' = y'…F \text{ and } G$ ("out of alphabetical order", but simpler condition first), followed by iii) and iv) as 3. & 4. above (in order). Anybody's guess…) – greybeard Jan 26 '17 at 22:25
• @greybeard The two steps seem independent, so the order probably does not matter? More interesting question: x' is part of the "current record" of file F. After 1., has x' changed by advancing F (still "current") or not? If you'd code it with current standards, the latter; but I'd have to think or test in more detail to make sure. – Raphael Jan 27 '17 at 6:59
• @Raphael: still "current" - current one, always, different from before or not, the way I read it. advancing F (or G, H, at that): between iterations or as last part of step? (and why doesn't H have to be replaced?) I can't remember implementing this… – greybeard Jan 27 '17 at 8:14

The authors assume that the data can be sorted so there has to be some (total) order relation $\leq$ (canonically) on the elements. We don't care what the elements are, so we do not fix the relation, either. In any given situation, we would know what to do and have a fixed relation.
For instance, if we wanted to sort natural numbers in increasing order, $>$ would mean the usual. I we wanted to sort them in decreasing order, you'd have to replace $>$ by $<$ in the solution.