# Quick Algorithm Question

• 11-01-2007
cjwenigma
Quick Algorithm Question
What is the difference between a sorting algorithm that is considered to be stable versus one that is unstable?

I know that stable and unstable refer to the action that is taken when two values compare as equal. I wanted a more watered down version though so I can understand this better.
• 11-01-2007
anon
Stable sort will leave equal elements in their original relative order.
• 11-01-2007
robatino
The stable sort leaves unchanged the relative order of elements which are equivalent (not necessarily equal) under the sort relation. The standard STL sort algorithms require a strict weak ordering as a sort relation, which allows nonequal elements to be equivalent. For example, the relation R such that x R y iff |x| < |y| is a strict weak ordering, but 5 and -5 are equivalent under it.
• 11-01-2007
brewbuck
Imagine you had some set of records which you are trying to sort based on a specific key element -- say, Age. You already have a set of these records in some specific order, and you want to STABLY sort them based on Age. For instance, say you had this:

Code:

```Maria, 25 Dan, 29 April, 29 Bob, 19 Tim, 25```
After a stable sort on Age, these items are in the following order:

Code:

```Bob, 19 Maria, 25 Tim, 25 Dan, 29 April, 29```
This is "stable" because Maria still comes before Tim, Dan still comes before April. An unstable sort might have produced:

Code:

```Bob, 19 Tim, 25 Maria, 25 April, 29 Dan, 29```
It's still sorted, but Tim now comes before Maria and April comes before Dan. This is "unstable."