Does stable_sort() also preserve the order of unequal elements?

Question

From cppreference, I know that for stable_sort:

The order of equal elements is guaranteed to be preserved.

I also read this question What is stability in sorting algorithms and why is it important? and understand the concept and basic usage of stability.

Here's how I understand stable sort:
Let's say I have unordered flight departure time and destination.

First, I sort it by time. It would be like

d-time dest
   1     A
   2     B
   3     C
   4     A
   5     B

Then stable sort by dest. It would be like

 dest   d-time
   A     1   (stable sort guarantee that [A,1] comes before [A,4])
   A     4
   B     2   (stable sort guarantee that [B,2] comes before [B,5])
   B     5
   C     3

---

But an example C++ Primer seems to indicate that stable_sort also guarantee the order of previous unequal elements (if so, it means stable_sort keeps all the original order).

Sample code:

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;

bool isShorter(const string &s1, const string &s2)
{
    return s1.size() < s2.size();
}

int main(int args, char *argv[])
{
    vector<string> words;
    string in_word;
    istringstream isin("the quick red fox jumps over slow turtles");
    while (isin >> in_word) {
        words.push_back(in_word);
    }
    sort(words.begin(), words.end());
    auto end_unique = unique(words.begin(), words.end());
    words.erase(end_unique, words.end());

    stable_sort(words.begin(), words.end(), isShorter);

    for (auto &s : words) {
        cout << s << " ";
    }
    cout << endl;
} 

Here's the text makes me question that whether stable_sort keeps all the original elements' order.

Assuming words was in alphabetical order before this call (the first sorting and erasing function calls), after the call, words will be sorted by element size, and the words of each length remain in alphabetical order. If we run this code on our original vector, the output will be
fox red the over slow jumps quick turtle

After first sorting and erasing, I have:
fox jumps over quick red slow the turtles

After stable sort, I have:
fox red the over slow jumps quick turtle

---

So my question is:

For stable_sort, just see the first 3 elements:

fox red the, is this order fixed? Or it's just one possible order among the arrangements:

fox red the fox the red the red fox the fox red ... (6 results)

I mean, the document only said stable_sort keeps the original order of equal elements. fox red the are not equal. They have order. But from the quoted text and output, it seems to indicate that It simply keeps all the original order.

Do I misunderstand something or the textbook is wrong here and the output is just happened to follow the previous sorting order?

Answer 1

fox, red, and the are equal for the purposes of the stable_sort. The cppreference link you have says:

Elements are compared using the given comparison function comp.

So, yes the fox red the order is fixed for your example, as the stable_sort won't change the relative order of those three (equally short) items.

Answer 2

It would probably be more precise to say that the order of equivalent elements is guaranteed to be preserved. Or even more exactly, stable_sort preserves the order of elements that are equivalent with respect to the ordering comparison used for the sort.

Like many standard algorithms, std::stable_sort requires the comparison method to be used to be a Strict Weak Ordering on the elements in the range. This is true both for the versions that use operator< and for the versions that use a passed Compare object. Part of the definition of a Strict Weak Ordering is that the binary relation determined by !(x<y || y<x) or !(comp(x,y) || comp(y,x)) is an Equivalence Relation.

So in your first example, two of your elements are [A,1] and [A,4]. In the context of the stable sort by destination, presumably your comparison functor would return false for both comp([A,1], [A,4]) and comp([A,4], [A,1]), so the elements are equivalent. But we can say they are not equal, in the sense that they are not identical. (Note this is all entirely independent of the meaning of any operator== or operator!= function for the element type, if such a thing is even defined at all.)

In the word sorting example, "fox" and "red" are equivalent with respect to isShorter, because isShorter("fox", "red") and isShorter("red", "fox") are both false. So the stable_sort call using isShorter must preserve the fact that "fox" comes before "red". But again, these two words are clearly not identical. And yes, the order fox red the is fixed, because the sort must preserve the relative ordering of all these words from the same equivalence class. On the other hand, "red" and "jumps" are not equivalent, since isShorter("red", "jumps") is true, so the sort needs to swap orderings so that "red" ends up somewhere earlier than "jumps".

In fact, for any range and valid Strict Weak Ordering comparison, there is only one allowed result of std::stable_sort (unlike std::sort, which would be correct given any reordering of each equivalence class of elements in the sequence).