# Could graph theory aid in the understanding of comparison sorting algorithms?

I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article.

Up to $n=15$, we know how many comparisons between elements one must make to be sure the list is sorted. This sequence of numbers can be found here. The entry in OEIS does not mention exactly which elements should be compared (and when), though. I guess this is mentioned in the article it refers to, but I am not certain, since I don't have the moment and they don't seem to be available for free.

But let's suppose we do know which elements should be compared. Then we can write up a list of pairs of these elements. Then, we could visualize these pairs by drawing a graph, in which each node represents an element of the list (that ought to be compared with another element in order to sort the list) and each vertex between two elements represents a comparison between two elements of the list that must be compared in order to sort the list.

Q: I am wondering if we could deduce anything from these graphs, by putting them side by side. Do any patterns emerge? Could we extrapolate how the graphs for $n>15$ might look like?

-

The fact that OEIS lists only 15 results is a pretty good indicator that nobody knows how to understand optimal comparison sorting strategies well enough to continue the list sequence now. Therefore, nobody knows either which approach will or won't eventually crack the problem.

A concrete problem with the approach you sketch is that you seem to be assuming that we'll first decide in detail which pairs of elements to compare and only then do all the comparisons. But that's not actually how it goes -- any sorting algorithm that makes fewer than $\frac{n(n-1)}{2}$ comparisons must adjust it choices of which elements to compare based on the results of previous comparisons. And then the algorithm cannot be represented as simply as you propose here.

There's a lot of graph intuition that goes into sorting, though. For example, one may consider a directed graph that represents our knowledge of the true order of elements at any step in the algorithm. This would have the elements to be sorted as vertices and the transitive closure of the answers we've gotten so far as edges. A sorting strategy could then be represented as a set of isomorphism classes of such graph, each together with an indication of which comparison to do next. The algorithm would be to do a comparison, update our graph-of-knowledge and then find its isomorphism class in the strategy. (This would be slow in practice, but that doesn't matter because the term "comparison sorting" implies that the only cost we're interested in is the comparisons themselves, not whatever other administrative computation we need to do).

-

I'm afraid I have a pessimistic view of your approach. The goal of sorting is to resolve the conflict between the "internal" ordering on the objects (their order), and the "external" ordering on the objects (their position in the list). Hence any graph you produce would be highly dependent on both of these orderings. Further, most algorithms are dynamically determined; depending on the outcome of comparison #3, we may choose different elements for comparison #5.

One thing that could be easily visualized with the graph is roughly how many comparisons are made, but it seems a lot of work for a single data point.

-
O.K. , if this is true, it's a pity. I thought asking tis question might be worth a shot. Thank you for this answer though. – Max Muller May 1 '13 at 13:11
this* question. – Max Muller May 1 '13 at 13:47
The positions in the input list is kind of a red herring here, because a the level of abstraction we're talking about here, "comparison sorting" is not really about rearranging elements of a list physically, but just about discovering their ordering relation using a minimal number of queries. Once this ordering is fully know, actually putting the elements in the sequence it indicates is considered a trivial matter. – Henning Makholm May 1 '13 at 14:21