Our first permutative algorithm: std::sort

So far all the algorithms we've covered simply walk through their given ranges in order, linearly, from one element to the next. Our next family of algorithms doesn't behave that way. Instead, it takes the values of the elements in the given range and shuffles them around so that the same values still appear, but in a different order. The mathematical name for this operation is a permutation.

The simplest permutative algorithm to describe is std::sort(a,b). It does what the name implies: sort the given range so that the smallest elements appear at the front and the biggest elements at the back. To figure out which elements are "smallest," std::sort(a,b) uses operator<.

If you want a different order, you could try to overload operator< to return true under different conditions--but probably what you should do is use the three-argument version of the algorithm, std::sort(a,b,cmp). The third argument should be a comparator; that is, a function, functor, or lambda that returns true whenever its first argument is "smaller" than its second argument. For example:

    std::vector<int> v = {3, 1, 4, 1, 5, 9};
    std::sort(v.begin(), v.end(), [](auto&& a, auto&& b) {
      return a % 7 < b % 7;
    });
    assert((v == std::vector{1, 1, 9, 3, 4, 5}));

Notice that I carefully chose my lambda in this example so that it would sort the array in a deterministic way. If I'd chosen the function (a % 6 < b % 6) instead, then there would have been two possible outputs: either {1, 1, 3, 9, 4, 5} or {1, 1, 9, 3, 4, 5}. The standard sort algorithm doesn't guarantee anything about the relative position of elements that happen to be equal under the given comparison function!

To fix this problem (if it is a problem), you should replace your use of std::sort with std::stable_sort. The latter might be a little slower, but it will guarantee that in the case of equal elements the original order is preserved--that is, in this case we'll get {1, 1, 3, 9, 4, 5} because in the original (unsorted) vector, element 3 came in front of element 9.

There's an even worse thing that can happen with sort and stable_sort--what if I had chosen the comparison function (a % 6 < b)? Then I would have had certain pairs of elements x, y where x < y and simultaneously y < x! (One such pair of elements in the original vector is 5 and 9.) In this case, there's nothing that can save us; we've passed in a "comparison function" that simply isn't a comparison function! This is a violation of the preconditions of std::sort, just as if we'd passed it a null pointer. When sorting an array, make sure you're sorting it based on a comparison function that makes sense!