Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
29  
This question would be easily answered within a minute with wikipedia. en.wikipedia.org/wiki/Sorting_algorithm –  Mare Infinitus Jul 9 at 21:42
5  
@MareInfinitus More precisely : en.wikipedia.org/wiki/Sorting_algorithm#Stability –  BЈовић Jul 10 at 9:40
3  
This is a question lacking own research. Answered with a wikipedia picture. And it gets really good feedback, which somehow makes me sad. IMHO it should be closed, and not get upvotes. –  Mare Infinitus Jul 10 at 14:51
3  
On the other hand, I just saw this and learned something new. If I had known that I didn't know this then I could have researched it but because the OP asked the question I now know what I didn't know that I didn't know. –  Kazark Jul 10 at 17:28
1  
Generally, "just google it" or "look it up on wikipedia" are not considerable acceptable responses on StackExchange sites. Because they do not provide an answer to what the complainer is verifying as a valid question with the call to the authorities of google and wikipedia. IF the question is easily a duplicate of another question or questions within programmers.stackexchange, then you can complain. –  Michael Paulukonis Jul 14 at 20:00

2 Answers 2

up vote 63 down vote accepted

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.

enter image description here

share|improve this answer
29  
Correction: The unstable algorithm exhibits undefined behaviour when two elements are equal, it is perfectly possible that the order is sometimes preserved. –  eBusiness Jul 9 at 21:16
4  
Nice picture, very similar to wikipedia en.wikipedia.org/wiki/Sorting_algorithm –  Mare Infinitus Jul 9 at 21:43
7  
@MareInfinitus: It's in the public domain. Check the attribution on the original image. –  Robert Harvey Jul 9 at 21:43
1  
A good picture explains faster and deeper than a lot of words on the average case. Legal issues were not what I wanted to talk about. –  Mare Infinitus Jul 9 at 21:45
3  
@RobertHarvey Actually, I believe the editor is correct. Your post currently says that a stable sort preserves the ordering of cards in the same suit, but cards in the same suit will have different ranks and thus must be rearranged to achieve sorted order. For example the sort does not preserve the order of the 2 and the 5 of hearts. It's the ordering of cards with the same rank (and different suits) that makes the difference between stable and unstable. –  David Z Jul 11 at 5:03

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: {(6, 3), (5, 5), (6, 1), (1, 3)}

Stable Sorted: {(1, 3), (5, 5), (6, 3), (6, 1)}

Regular Sorted: Either {(1, 3), (5, 5), (6, 3), (6, 1)}, or {(1, 3), (5, 5), (6, 1), (6, 3)}


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.

share|improve this answer
2  
Is it less efficient though? It seems "obvious", but some of the best sorting algorithms are stable by nature (e.g. anything based on merge sort, such as Tim sort), they don't need to do any explicit extra work to be stable. –  delnan Jul 9 at 21:25
9  
Stable has nothing to do with performance in general. Mergesort runs in O(n*log n) and is stable. Heapsort has similar performance, but is not stable. –  Mare Infinitus Jul 9 at 21:37
1  
"Stable" can also apply to data-structures, eg. a "stable heap" is a heap which dequeues items that have the same priority in the same order they were queued. This is very important for efficient path-finding algorithms. –  BlueRaja - Danny Pflughoeft Jul 9 at 23:08
    
There are no stable sorts which are O(n ln n) comparisons and also O(1) on memory. Speed is not the only measure of efficiency. The fact that you can't stable sort in-place matters. –  QuestionC Jul 10 at 13:40
2  
@QuestionC It appears block sort is stable and fits those bounds. –  delnan Jul 10 at 15:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.