In reading about various sorting algorithms I've seen it mentioned that some are "stable" and some are not. What does that mean, and what tradeoffs are involved on that basis when selecting an algorithm?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
A stable sort is one which preserves the original order of the input set, where the comparison algorithm does not distinguish between two or more items.
Consider a sorting algorithm that sorts cards by rank, but not by suit. The stable sort will guarantee that the original order of cards having the same rank is preserved; the unstable sort will not.
Stable algorithms preserve the relative order of elements.
So a stable sorting algorithm will retain the relative order of values which compare as equal.
Consider a sorting algorithm where we sort a collection of 2d points based on their X dimension.
Collection to be sorted:
Regular Sorted: Either
As for the tradeoff... well, stable sorting is less efficient, but sometimes you need it.
For example when a user clicks the a column header to sort values in a UI, it's reasonable to expect his previous sorting order to be used in the case of equal values.