Ned Batchelder writes:
On 1/17/14 8:45 AM, אלעזר wrote:
"Informally, an algorithm is stable if it respects the original order of equivalent objects. So if we think of minimum and maximum as selecting, respectively, the smallest and the second smallest from a list of two arguments, stability requires that when called with equivalent elements, minimum should return the first and maximum should return the second."
I don't understand this logic at all. Stability matters in sorting because sort() takes a sequence and returns a sequence, and for various reasons you might need to sort a list twice, with different criteria. Stability guarantees that the second sort won't discard the work of the first sort.
Two comments. First, I don't understand at all why earlier members of a sequence may be presumed to be smaller. It could easily go the other way around. Second, since these operations are *selections* from a collection (which might impose order or not, which might impose uniqueness or not), it's the same problem that Steven d'Aprano faced in defining mode for the statistics PEP: Do you admit failure (here, noncomparability of some of the maximal items), so that a value that is none of the items must be returned? In the case of multiple equivalent values, do you return a representative or the collection?