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.