What is the difference between std::sort and std::stable_sort?

Question

I would like to know how std::sort and std::stable_sort differ with respect to functionality, memory and hardware? The documentation mentions that "Sorts the elements in the range [first,last) into ascending order, like sort, but stable_sort preserves the relative order of the elements with equivalent values.", but that didn't make sense to me. What is the "relative order" and "equivalent values"?

Answer 1

Yes, it's as you said, and this is not a concept unique to C++.

Stable sorts preserve the physical order of semantically equivalent values.

---

std::sort:

The order of equal elements is not guaranteed to be preserved.
Complexity: O(N·log(N)), where N = std::distance(first, last) comparisons

std::stable_sort:

The order of equal elements is guaranteed to be preserved.
Complexity: O(N·log^2(N)), where N = std::distance(first, last) applications of cmp. If additional memory is available, then the complexity is O(N·log(N)).

The implication is that std::stable_sort cannot be performed quite as efficiently in terms of execution time, unless "additional memory is available" in which case it is not being performed as efficiently in terms of memory consumption.

Answer 2

As mentioned, the standard only notes that std::stable_sort preserves the original order for equal elements, while std::sort doesn't.

In the case of HP / Microsoft STL, std::sort is usually quick sort, unless the nesting gets too deep, in which case it switched to heap sort. Quick sort time complexity is typically O(n log(n)), but it's worst case is O(n^2), which is avoided with the switch to heap sort, since heap sort is always O(n log(n)) (but slower than quick sort so it's only used to avoid O(n^2)).

In the case of HP / Microsoft STL, std::stable_sort is a hybrid bottom up merge sort, using insertion sort to create sorted groups of 32 elements, then doing bottom up merge sort with the groups. The array (or vector) is split into two, a temporary array (or vector) 1/2 the size of the array to be sorted is allocated, and used to do a merge sort for both halfs of the array. Then one of the half arrays is moved to the temp array to do a final merge pass. Merge sort is also O(n log n), taking a bit longer for sorting arrays of objects, but merge sort is often faster if sorting an array of pointers to objects where a comparison function is included in the call. This because merge sort involves more moves but fewer compares than quick sort.

For sorting an array of integers, a radix sort is faster. If sorting by byte, then it takes 4 passes to sort an array of 32 bit integers, and 8 passes to sort an array of 64 bit integers.