38

Can someone explain what "stable" and "unstable" mean in relation to various sorting algorithms> How can one determine whether an algorithm is stable or not, and what applications do unstable sorting algorithms usually have (since they are unstable)?

Ashley Pinkman
  • 467
  • 1
  • 4
  • 7

2 Answers2

64

If a sorting algorithm is said to be "unstable", this means that for any items that rank the same, the order of the tied members is not guaranteed to stay the same with successive sorts of that collection. For a 'stable' sort, the tied entries will always end up in the same order when sorted.

For an example of applications, the quick sort algorithm is not stable. This would work fine for something like sorting actions by priority (if two actions are of equal priority, you would not be likely to care about which elements of a tie are executed first).

A stable sorting algorithm, on the other hand, is good for things like a leaderboard for an online game. If you were to use an unstable sort, sorting by points (for instance), then a user viewing the sorted results on a webpage could experience different results on page refreshes and operations like paging through results would not function correctly.

  • 4
    edited to include some examples of why the difference matters. –  Feb 28 '13 at 01:03
  • 3
    Unusable sorts usually produce predictable results, ie they will not give different answers given the same data. So page refreshes will only show different order for equals when other values change. The cause of the instability is in the use of trees or some similar data structure when organizing the data. – Peter Wooster Feb 28 '13 at 01:16
  • 3
    Its worth noting that a more common usage of stable sorts is sorting by multiple keys. For example, if you have an array of objects representing people, and you want it sorted by their age, with ties broken by names (alphabetic), then you could sort first by name, and then by age, and a stable sort would have it in the state you're looking for. – Aaron Dufour Feb 28 '13 at 02:35
  • MIB is stable sort. (M-> MergeSort, I-> InsertionSort, B-> BubbleSort) – roottraveller Nov 07 '16 at 10:03
8

A stable sort retains the order of identical items. Any sort can be made stable by appending the row index to the key. Unstable sorts, like heap sort and quick sort for example do not have this property inherently, but they are used because they tend to be faster and easier to code than stable sorts. As far as I know there are no other reasons to use unstable sorts.

Rafay
  • 6,108
  • 11
  • 51
  • 71
Peter Wooster
  • 6,009
  • 2
  • 27
  • 39
  • Going to the point above that Azron had made(below your point) and the example that he has taken, does that mean grid sorting that we do in windows is implemented in one of the stable sort? Grid sorting means, sorting the files in folder by date and type. – Bhupesh Pant Jan 14 '14 at 13:29
  • 2
    sorts done in things like the file manager and excel are stable, they either use a stable sort or the stabilized version of one of the unstable sorts. – Peter Wooster Jan 14 '14 at 23:46