When do you call stable_sort() on scalars?

Question

Is it ever good to call stable_sort instead of sort on scalar types (i.e. int, long, etc.) with the default comparator?

If so, when should you do this?

If not, then why don't standard libraries just forward such calls to sort? Wouldn't that be much faster?

Answer 1

Stable sorts are really only useful when the items you are sorting have satellite information.

---

From CLRS (Introduction to Algorithms, 3rd Ed.):

"In practice, the numbers to be sorted are rarely isolated values. Each is usually part of a collection of data called a record. Each record contains a key, which is the value to be sorted. The remainder of the record consists of satellite data, which are usually carried around with the key. In practice, when a sorting algorithm permutes the keys, it must permute the satellite data as well."

---

When a sort is stable, it means that ties are broken in the sorted array by the items' original ordering. If you are only sorting int and long types, you don't need a stable sort.

Answer 2

There should be no difference (maybe with exception of things like -0.0 and 0.0). However I do not think there is any need to forward such calls, because std::sort or std::stable_sort should not know what they are sorting, so long as the comparison operation compiles. These functions don't need to be too smart.

Answer 3

With the default comparator specifically (implying the natural strict ordering)? I don't see any use for stable sorting on scalars in that case. Stable sorting can't provide any additional benefits in situations when equivalent values (according to the comparator) are indistinguishable. (Although @Andrey Tuganov in his answer makes an interesting and relevant remark about negative zeros).

Nevertheless stable sorting on scalars might be useful when the ordering criterion is weaker than the natural strict ordering. For example, you can write a comparison predicate that will say that any odd number is greater than any even number. In that case the resultant ordering will simply partition the array into contiguous blocks of even and odd numbers (in that order). If you are interested in keeping the relative order of these numbers unchanged, you need stable sorting algorithm.