The story of finitary deterministic comparison sorting is well-known: we have the naive $O(n^2)$-time algorithms like selection and insertion sorts; once we try divide-and-conquer recursion we immediately achieve the theoretically optimum time complexity of $O(n \log n)$. In this case it's the number of comparisons which is the bottleneck, and the exact list model we use doesn't matter, given that the list operations are blind to the ordering of the elements they carry.
My question is: what is the analogous story for transfinite comparison sorting? Consider well-ordered sequences of characters from a well-ordered alphabet.
Note: for the time being, let us consider sequences of distinct characters for simplicity.
Each such sequence has a unique sorted permutation, and it's not hard to define a reasonable model of comparison sorting (see below). However, the story is different. Some things are simpler: I suspect $O(n \log n)$ has no meaningful extension to a transfinite complexity measure. Some things are more complex: the finitary quadratic time measure $O(n^2)$ can mean the (order type of the input)*(order type of the output), or the other way around.
What algorithms admit faithful transfinite extensions? Is there a "best" sorting algorithm? Is there a reasonable lower bound? If so, which operation is the bottleneck?
Model of comparison sorting:
Consider the following variation on ordinal register machines. A program has a finite number of registers, each of which stores a list, a character, or an ordinal (or may be undefined). A program consists of a finite list of lines. Each line of the program is either an assignment statement, a branching statement a goto statement, or a halt statement. We can test the relative order of two characters, we can test whether an ordinal is zero, and we can test whether an ordinal is less than the length of a list.
There is a designated input and output register, each of type "list." Initially the input stores a given list of distinct characters; at some ordinal stage, the program must halt with the output variable storing the unique sorted permutation of the input.
As for operations, we can at least increment ordinals and perhaps do some arithmetic on them. (If the answer depends on this choice, the question seems less robust that I had hoped.) Lists are arrays with direct access; we can read and write a character in a given list at a given index. We can also add a character to the beginning or end of a list, or at a particular list index. (Meaning, add the character to the given index, and shift all subsequent characters down by one.)
Semantics at successor stages is standard. At limit stages, program control goes to the lim inf, i.e., the least line that occurs cofinally often in the limit. Ordinal-valued registers take the lim inf of their values. Character-valued registers are, let's say, undefined in the limit.
The one important choice we have to make is the limiting behavior of list-valued registers. Let us say that
- A character occurs in the limit if it occurs in all sufficiently large stages below the limit.
- for two such characters $x$ and $y$, $x < y$ in the limit list if $x < y$ in all sufficiently large stages below the limit. (Here $<$ refers to the precedence ordering in the list.) If this does not define a linear order, then the limit is undefined.
Now, this model is flexible enough to implement natural transfinite extensions of insertion and selection sorts. The "time complexity" is simply the halting ordinal.
