47

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?

Improve this question
9
  • 32
    This question would be easily answered within a minute with wikipedia. en.wikipedia.org/wiki/Sorting_algorithm
    – Mare Infinitus
    Jul 9, 2014 at 21:42
  • 6
    @MareInfinitus More precisely : en.wikipedia.org/wiki/Sorting_algorithm#Stability
    – BЈовић
    Jul 10, 2014 at 9:40
  • 4
    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, 2014 at 14:51
  • 4
    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, 2014 at 17:28
  • 4
    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, 2014 at 20:00

2 Answers 2

Reset to default
93

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

Improve this answer
6
  • 41
    Correction: The unstable algorithm exhibits undefined behaviour when two elements are equal, it is perfectly possible that the order is sometimes preserved.
    – aaaaaaaaaaaa
    Jul 9, 2014 at 21:16
  • 9
    Nice picture, very similar to wikipedia en.wikipedia.org/wiki/Sorting_algorithm
    – Mare Infinitus
    Jul 9, 2014 at 21:43
  • 9
    @MareInfinitus: It's in the public domain. Check the attribution on the original image.
    – Robert Harvey
    Jul 9, 2014 at 21:43
  • 2
    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, 2014 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, 2014 at 5:03
26

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.

Improve this answer
9
  • 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.
    – user7043
    Jul 9, 2014 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, 2014 at 21:37
  • 2
    "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, 2014 at 23:08
  • 1
    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, 2014 at 13:40
  • 4
    @QuestionC It appears block sort is stable and fits those bounds.
    – user7043
    Jul 10, 2014 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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