Sorting algorithm

Builds on Algorithm Total order Permutation

Definition

Let $(X, \le)$ be a totally ordered set. A sorting algorithm for $X$ is an algorithm whose inputs are finite sequences $(a_1, \dots, a_n)$ over $X$ . On each input it outputs a sequence $(a_{\sigma(1)}, \dots, a_{\sigma(n)})$ such that:

$\sigma$ is a permutation of $\set{1, \dots, n}$ ;
$a_{\sigma(1)} \le a_{\sigma(2)} \le \cdots \le a_{\sigma(n)}$ .

The algorithm is stable if moreover $\sigma(i) < \sigma(j)$ whenever $i < j$ and $a_{\sigma(i)} = a_{\sigma(j)}$ . It is a comparison sort if it accesses the elements only through tests of the form $a_i \le a_j$ .

Remarks

In practice one often sorts records by a key, and $\le$ is then a total preorder on records. Stability matters only in that setting, or when equal elements can be told apart.

Example: on input $(3, 1, 2)$ , the output $(1, 2, 3)$ is correct, with $\sigma = (2, 3, 1)$ in one-line notation, so $\sigma(1) = 2$ , $\sigma(2) = 3$ , $\sigma(3) = 1$ .

Non-example: an algorithm that outputs $(1, 1, 2)$ on $(2, 1, 1, 3)$ fails clause 1, since its output is not a rearrangement of all four input elements. An algorithm that outputs its input unchanged fails clause 2 on $(2, 1)$ .

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Algorithm concept
Permutation concept
Total order concept
Sorting algorithm definition

Tag	`B6ADA6RGAM`
URI	`m2://B6ADA6RGAM`
Kind	definition
Writing	W0 stub
MSC	68P10, 68W40
Defines	Sorting algorithm
Uses	Algorithm, Total order, Permutation
Changed	3 November 2026

Sorting algorithm

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here