http://stackoverflow.com/questions/1517793/stability-in-sorting-algorithms

A sorting algorithm is said to be stable if two objects with equal keys appear in the
same order in sorted output as they appear in the input array to be sorted.

Suppose we have input:

peach
straw
apple
spork

Sorted would be:

apple
peach
straw
spork

and this would be stable because even though straw and spork are both ‘s’, their ordering is kept the same.

In an unstable algorithm, straw or spork may be interchanged, but in stable sort, they stay in the same relative positions (that is, since ‘straw’ appears before ‘spork’ in the input, it also appears before ‘spork’ in the output).

Examples of stable sorts:

mergesort
radix sort
bubble sort
insertion sort