
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.

Stable sort will leave equal elements in their original relative order.

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.

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."