## You are here

Homestable sorting algorithm

## Primary tabs

# stable sorting algorithm

A *stable sorting algorithm* is any sorting algorithm that preserves the relative ordering of items with equal values. For instance, consider a list of ordered pairs

$\displaystyle L:=\left\{(A,3),(B,5),(C,2),(D,5),(E,4)\right\}.$ |

If a stable sorting algorithm sorts $L$ on the second value in each pair using the $\leq$ relation, then the result is *guaranteed* to be
$\left\{(C,2),(A,3),(E,4),(B,5),(D,5)\right\}$. However, if an algorithm is not stable, then it is possible that $(D,5)$ may come before $(B,5)$ in the sorted output.

Some examples of stable sorting algorithms are bubblesort and mergesort (although the stability of mergesort is dependent upon how it is implemented). Some examples of unstable sorting algorithms are heapsort and quicksort (quicksort could be made stable, but then it wouldn’t be quick any more). Stability is a useful property when the total ordering relation is dependent upon initial position. Using a stable sorting algorithm means that sorting by ascending position for equal keys is built-in, and need not be implemented explicitly in the comparison operator.

## Mathematics Subject Classification

68P10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Lorenz system by David Bankom

Oct 19

new correction: examples and OEIS sequences by fizzie

Oct 13

new correction: Define Galois correspondence by porton

Oct 7

new correction: Closure properties on languages: DCFL not closed under reversal by babou

new correction: DCFLs are not closed under reversal by petey

Oct 2

new correction: Many corrections by Smarandache

Sep 28

new question: how to contest an entry? by zorba

new question: simple question by parag

Sep 26

new question: Latent variable by adam_reith

## Corrections

rendering by CWoo ✓

stable algorithm? by Mathprof ✓

suppress link by Mathprof ✓