Formulating list sorting as a pure math problem

Sorting a list is a classic problem in computer science, and many interesting algorithms such as merge sort and heap sort have been discovered.

I'd like to have a precise formulation of the list sorting problem as a pure math problem, so that a hypothetical pure mathematician who has never heard of computers (such as Gauss, let's say) would be able to read the problem, understand it, and then invent algorithms such as merge sort and heap sort.

A statement such as "devise an algorithm for sorting a list of numbers into ascending order" is inadequate, because it doesn't state which basic operations are allowed to be used by the algorithm. And it also doesn't say precisely what an "algorithm" is. Yes, it should be something that can be implemented in assembly code, but we are posing the problem for a mathematician who has never heard of a computer.

Once the problem has been formulated precisely, it should be possible to state and prove theorems such as "The worst-case running time of the quicksort algorithm is $$O(n^2)$$" with a level of precision and rigor that would meet the standards of, say, baby Rudin.

Question: How would you precisely state the problem of devising a list sorting algorithm?

Bonus question: Do you know of a reference that presents list sorting algorithms as a topic in pure math, with a level of precision that would satisfy an author such as Rudin?

Edit: This might make the question more specific. The beginning of chapter 8 of Introduction to Algorithms by Cormen et al [p. 191 in the third edition] states:

These algorithms share an interesting property: the sorted order they determine is based only on comparisons between the input elements. We call such sorting algorithms comparison sorts. All the sorting algorithms introduced thus far are comparison sorts.

In section 8.1, we shall prove that any comparison sort must make $$\Omega(n \lg n)$$ comparisons in the worst case to sort $$n$$ elements.

More specific question: How would you formulate that statement precisely as a math theorem -- the fact that any comparison sort must make $$\Omega(n \lg n)$$ comparisons in the worst case. In order to make this rigorous, we must either define precisely what a "comparison sort" is, or else avoid using the term entirely.

• We assume there is an algorithm that can compare any two items on the list and return something that tells which is the larger. We then compare sort techniques based on how many call there are to the algorithm. That seems like a fine specification to me. – Ross Millikan Jun 9 at 13:37
• @RossMillikan Would you be allowed, for example, to move the item in position $j$ to position $i$ in the list? Is that a basic operation that is allowed or must it be achieved by some combination of other basic operations? – littleO Jun 9 at 13:44
• You are generally allowed to manipulate the list any way you want. The assumption is that this takes no time compared to comparing elements. – Ross Millikan Jun 9 at 13:46
• This is not a precise statement, though. What does "any way you want" mean. Also, if the list is an array of numbers in computer memory, moving the item in position $j$ into position $i$ requires moving a lot of stuff around in memory (because many items in the array must be shifted by one position), and it's not clear that this cost is negligible. – littleO Jun 9 at 13:50

There are several mathematical studies of sorting algorithms, starting from Knuth's bible [3] on the topic. The Handbook [2] also offers a rigorous approach to algorithms and gives a number of references.

I will not try to summarize in a few lines the 790 pages of Knuth's volume, but here are some points to take into account for a mathematical approach to sorting.

1. You are given a totally ordered $$n$$-element set $$S = \{a_1 < a_2 < \ldots < a_n\}$$. Initially the array to be sorted is $$(a_{\sigma(1)}, a_{\sigma(2)}, \ldots, a_{\sigma(n)})$$, where $$\sigma$$ is a permutation of $$\{1, \ldots, n\}$$.
2. Usually, the (time) complexity measures the number of comparisons needed to sort the array. No other parameter is taken into account. Thus comparisons of the form "is $$a < b$$?" are the only basic operations considered. This way, the problem is totally independent of the implementation.
3. There are several complexity measures, including time-complexity (including worst case time-complexity), average time-complexity, space complexity (which measures the amount of memory used by your algorithm), not to speak about the more recent amortized computational complexity. In your question, you seem to be interested in the worst case time-complexity.
4. [EDIT] The minimal number of comparisons needed to sort $$n$$ elements is OEIS sequence A036604. See [4] for a recent contribution on this topic.

In a comment, you claim that

if the list is an array of numbers in computer memory, moving the item in position $$j$$ into position $$i$$ requires moving a lot of stuff around in memory (because many items in the array must be shifted by one position).

This is not true. For instance you can play around with pointers in C (or references in Java). Furthermore, a number of sorting algorithms are based on swapping two positions $$i$$ and $$j$$, which does not need any shift. To familiarise yourself with algorithms, [1] is one of the standard references, but they are many other ones.

[1] Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L. and Stein, Clifford. Introduction to algorithms. Third edition. MIT Press, Cambridge, MA, 2009. xx+1292 pp. ISBN: 978-0-262-03384-8

[2] Gonnet, Gaston H. and Baeza-Yates, R., Handbook of algorithms and data structures. 2nd ed. (English) International Computer Science Series. Bonn etc.: Addison-Wesley Publishing Company. XIV, 424 p. (1989).

[3] Knuth, Donald E. The art of computer programming. Vol. 3. Sorting and searching. Second edition. Addison-Wesley, Reading, MA, 1998. xiv+780

[4] Peczarski, Marcin (3 August 2011). Towards Optimal Sorting of 16 Elements. Acta Universitatis Sapientiae 4 (2): 215–224

• Thanks for the answer. Let's say we have an array (a contiguous block of computer memory) that stores the values $-3, 1, 7, 3, 5, 9, 2$. And we want to move the item in position 6 to position 2, so now the values in the array are going to be $-3, 1, 2, 7, 3, 5, 9$. That requires moving a bunch of stuff around in memory, right? – littleO Jun 9 at 17:11
• This has nothing to do with your question, as it depends on the data structure you are using. An array is not necessarily a contiguous block of memory. You can perfectly sort the addresses of the $n$ elements of your array, and then copy everything in a new block of memory if you wish at the very end. – J.-E. Pin Jun 10 at 3:29