There are two kinds of sort algorithms: "stable sorts" and "unstable sorts". These terms refer to the action that is taken when two values compare as equal. If you have an array T0..size with two elements Tn and Tk for n < k, and these two elements compare equal, in a stable sort they will appear in the sorted output with the value that was in Tn preceding Tk. The output order preserves the original input order. An unstable sort, by contrast, there is no guarantee of the order of these two elements in the output.
"What difference does it make?" you may ask. After all, if I have an input sequence 1 7 3 4 3 5 2, and the output sequence is 1 2 3 3 4 5 7, what does it matter that the values 3 may be in a different order? Well, consider that what we have is not a set of simple scalar values, but a set of tuples: <year, name>. Suppose my input sequence is <1981, "Fred">, <1987, "Joe">, <1983, "Harry">, <1984, "Charles">, <1983, "Ellen">, <1985, "Mary"> and <1982, "Harriet">. Suppose that I only compare the year. Then in a stable sort, I am guaranteed that the output will be <1981, "Fred">, <1982, "Harriet">, <1983, "Harry">, <1983, "Ellen">, <1984, "Charles">, <1985, "Mary">, <1987, "Joe">. You have the guarantee that the order of the two 1983 entries in the output preserves the original order. In an unstable sort, you have no such guarantee, and those two elements might well have come out as <1983, "Ellen">, <1983, "Harry">.
Note that qsort is not specified as a stable sort. Whether it is or not is up to a particular implementation.
Comments