Which of these is the best definition for a stable sorting algorithm?

An algorithm that does not change the relative ordering of records with identical keys
  • An algorithm that is as fast as the best one known
  • An algorithm that always gives the right answer
  • An algorithm that always gives the same order for duplicate keys from run to run

"Stable" has nothing to do with how fast an algorithm is.

It refers to maintaining the relative order of records with equal key values.

In some applications, we require that records with equal key value preserve the relative order of those records.