Sorting based on pairwise comparison

Input

1. An ordered sequence [math]\displaystyle{ S }[/math] of length [math]\displaystyle{ n }[/math].
2. A definition of comparison on the component type of [math]\displaystyle{ S }[/math].

Output

A permutation of [math]\displaystyle{ S }[/math] such that [math]\displaystyle{ S[i] \le S[i+1] }[/math] for all [math]\displaystyle{ i\in \{1,...,n-1\} }[/math].

Objective

N/A

Complexity

Polynomial.

Known algorithms

1. Bubblesort
2. Mergesort
3. Quicksort
4. Selection sort

Remark

Some algorithms could be formulated in a much simpler way in case each key occurs at most once in [math]\displaystyle{ S }[/math]. Here all algorithms are formulated for the general case of arbitrary multiplicities. Alternatively, there are three options to make each key unique:

1. An additional generated key such as, for example, student ID or tax file number.
2. If the keys are associated with values, they are additionally compared if the keys of two items are identical (e.g. date of birth and home address, if last and first names of two persons are identical).
3. On the other hand, if the keys are not associated with values, we may remove the duplicates and store their multiplicities separately.