Sorting an array using the topological sort of a corresponding comparison graph (Q2207498)

The main result of the paper is an algorithm that sorts an array \(A\) of size \(n\) in \(O(n\log{n})\) time, based on a representation of the relative order of some pairs of elements of \(A\) through a directed graph. For each index \(0\leq i\leq n-1\) of \(A\), the idea is to (cyclically) compare \(A[i]\) with the two elements that lie before and after it in \(A\). These comparions are encoded into a digraph \(G\) whose vertices are the elements of \(A\) and in which there is an arc from one element of \(A\), say \(u\), to the other, say \(v\), if \(u<v\). The proposed sorting algorithm realizes the following steps: first, construct the digraph \(G\) from \(A\) as described above. Apply a DFS on \(G\), and collect the DFS forest that ensues. Iterate merging of trees, DFS and DFS forest collection, until the undirected underlying graph that is obtained is connected. A final processing of the resulting digraph gives the elements of \(A\) in sorted (ascending) order. The proposed algorithm runs in \(O(n\log{n})\) time. This paper is written in a very unusual way. It looks like a student's manuscript that has slightly been adpated to become (but does not really conform to the standards of) a research paper. At times, it is overly long and detailed (e.g., Section 7). In particular, many definitions and some examples could have been removed, as they are folklore or trivial (e.g., Definitions 10 and 11). The paper is 24 pages long, but could have been much shorter. Having said that, the paper is easy to read. The ideas that are developed are standard and can easily be understood. It is not clear to me, though, whether the result is particularly innovative or sheds some new light, either on sorting itself, or on the relationships between graph and sorting algorithms.