What does > mean in this TAOCP solution?

Question

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:

3. If $x' > y'$, advance file $G$.
4. 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?

Answer 1

What does > denote here?

It's not stated explicitly, but a reasonable meaning can be inferred from context.

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.