Sorting

Sorting is a well-known problem which is encountered almost everyday in our (“analogical” and “digital”) lives.
For instance, when we organize our personal library we are used to collect books according to a specific order (e.g., issue volume number). Similarly, when we search the Web we are provided with a ranked (i.e., ordered) list of web page results, which the search engine thinks are the most relevant to our query. Not only, we may want the website of our bank to show us a timely-oredered sequence of account operations (i.e., from the newest to the oldest), and so on and so forth.
From all the examples above, it is clear that sorting implies having a notion of ordering.

More formally, sorting can be defined as follows:
Let $A=\{a_1,\ldots,a_n\}$ be a set of $n$ items and suppose there exists a total order binary relation $R_{\leq}$ over $A$, which is antisymmetric, transitive, and total, namely such as it holds the following $\forall a_i, a_j, a_k \in A$:
$a_i~R_{\leq}~a_j \wedge a_j~R_{\leq}~a_i \Rightarrow a_i = a_j$ (antisimmetry);
$a_i~R_{\leq}~a_j \wedge a_j~R_{\leq}~a_k \Rightarrow a_i~R_{\leq}~a_k$ (transitivity);
$a_i~R_{\leq}~a_j \vee a_j~R_{\leq}~a_i$ (totality).
The set $A$ together with the total order binary relation $R_{\leq}$ is also called totally ordered set.

A relation having the property of “totality” means that any pair of elements in the set are comparable under the relation. This also means that the set can be diagrammed as a “line of elements”, giving it the name linear. Totality also implies reflexivity, i.e., $a_i~R_{\leq}~a_i$. Therefore, a total order is also a partial order, which has a weaker form of the third condition (it only requires reflexivity, not totality).

Due to its intrinsic value (and perhaps due to the complexity of solving it efficiently), the sorting problem has gained a lot of attention among computer scientists since the origin of the discipline.
A sorting algorithm is an algorithm that operates on a list of items as input and returns the same list where items appear in a certain order as output. The most-used orders are numerical order and lexicographical order, so that:
– The output is in non-decreasing order (i.e., each element is no smaller than the previous element according to the desired total order);
– The output is a permutation (i.e., reordering) of the input.

A naïve, brute-force solution will enumerate all the possible permutations of the input list and then choose the one that is ordered. However, it turns out this strategy would be computationally unfeasible. Indeed, assuming the input list is $A=\{a_1,\ldots,a_n\}$ with no duplicates (similar considerations can be drawn if $A$ contains duplicates), the total number of permutations of $A$ is $n!$.

Sorting algorithms can be classified on the basis of several aspects (e.g., comparison- vs. integer-based, stable vs. unstable, etc.). Please, refer to this for an exhausitve taxonomy.

In this section, I will give you an overview of the most famous sorting algorithms proposed so far. Unless otherwise specified, I am assuming each algorithm takes as input an array of integers $A=[a_1,\ldots,a_n]$ (at the beginning randomly-ordered), and produces as output the same array $A$ where elements are in non-decreasing order (i.e., such that $a_i \leq a_{i+1}~\forall i\in\{1,\ldots,n-1\}$).

Note that for sorting, either a weak order (i.e., “should not come after”) or a strict weak order (i.e., “should come before”) can be specified. Also, for the sorting to be unique, these two are restricted to a total order and a strict total order, respectively.