sort: Put Things in Order, and Say Which Order You Mean

Kenji's bookshop has 100,000 prices to put in order for its new catalogue. Kenji likes speed, so he wrote his own sort by hand: an insertion sort, which takes each price and slides it left until it fits. On Compiler Explorer's GCC 12 it took 872 to 2,432 ms in nine runs. std::sort, one line, sorted the same 100,000 numbers in 5.7 to 7.5 ms. Kenji had optimised before he had measured. This lesson is about that one line, and about telling it which order you mean.

sort(v.begin(), v.end()): from the first item up to the end

sort lives in the header <algorithm>. It takes two iterators, the markers for places that Module 2 used. prices.begin() marks the first price. prices.end() marks the place just after the last one, so the range runs from the first item up to, not including, end(). sort puts every item in that range into increasing order, inside the same vector.

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

int main() {
    vector<int> prices{40, 15, 55, 20, 35};
    sort(prices.begin(), prices.end());
    cout << "sorted:";
    for (int p : prices) {
        cout << ' ' << p;
    }
    cout << '\n';
    return 0;
}

sorted: 15 20 35 40 55

So sort(v.begin(), v.end()) sorts the whole vector in place, and end() is one step past the last item, never an item itself.

The one question sort asks

sort never looks at the whole vector at once. Again and again, it takes two items, a and b, and asks one question: must a come before b? With no rule given, that question is a < b. A function that answers it is called a comparator. The widget replays GCC 12's own sort on the five prices. A program on Compiler Explorer logged every question, and the widget shows them in the same order.

Eleven questions put five prices in order. Each "yes" made sort move an item to the left, and each "no" left it where it stood. For 16 items or fewer, GCC 12's sort is one insertion sort, the same idea as Kenji's. A bigger vector gets a faster plan first, and lesson 05 shows it. So sort itself has no idea what "in order" means: it asks, and it moves only what the answers say.

The syntax you need on day one

#include <algorithm>      sort and stable_sort
#include <functional>     greater

sort(first, last);                     increasing order, decided by <
sort(first, last, comp);               the order comp decides
stable_sort(first, last);              increasing, and equal items keep their order
stable_sort(first, last, comp);        the same, with your rule

sort(v.begin(), v.end());              the whole vector
sort(v.begin() + i, v.begin() + j);    places i to j - 1 only
sort(a, a + n);                        the first n items of an array
sort(v.begin(), v.end(), greater<int>());    decreasing order
sort(v.rbegin(), v.rend());            decreasing order, by sorting it backwards

So every call says where to start, where to stop, and, if you want, the rule.

An array: sort(a, a + n)

An array's name works as a pointer to its first item, as Learn C showed. a + 5 points just past the fifth item. A pointer can serve as an iterator, so sort(a, a + 5) sorts the first five items.

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

int main() {
    int a[] = {9, 4, 7, 1, 8};
    sort(a, a + 5);
    cout << "array:";
    for (int x : a) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

array: 1 4 7 8 9

So pointers are iterators too: a marks place 0, and a + 5 the place after the last item.

Strings sort by character codes

< on two strings compares them like a dictionary, one character at a time. The first character that differs decides, by its code in the ASCII table. Digits come before uppercase letters, and uppercase letters before lowercase ones.

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

int main() {
    vector<string> names{"zara", "Bob", "amara", "Kenji", "alice", "10", "9"};
    sort(names.begin(), names.end());
    cout << "sorted:";
    for (const string& name : names) {
        cout << ' ' << name;
    }
    cout << '\n';
    return 0;
}

sorted: 10 9 Bob Kenji alice amara zara

"10" comes before "9", because '1' (49) is less than '9' (57), and the second character never gets asked. Bob and Kenji come before alice, because 'B' is 66, 'K' is 75 and 'a' is 97. alice comes before amara at their second letter, 'l' before 'm'. So sorted strings are in character-code order, which is alphabetical only when every word has the same case.

High to low: greater<int>() or the reverse iterators

To sort high to low, change the question to "is a greater than b?". greater<int>() asks exactly that. Another way is to sort the vector read backwards: rbegin() and rend() are reverse iterators, which walk from the last item to the first.

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

void show(const char* label, const vector<int>& v) {
    cout << label;
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
}

int main() {
    vector<int> v{40, 15, 55, 20, 35};
    sort(v.begin(), v.end(), greater<int>());
    show("greater:", v);

    vector<int> w{40, 15, 55, 20, 35};
    sort(w.rbegin(), w.rend());
    show("rbegin: ", w);
    return 0;
}

greater: 55 40 35 20 15
rbegin:  55 40 35 20 15

Both lines agree. The second call made the backwards reading increase, so the forward reading decreases. So you never need to sort low to high and then print backwards: say "high to low" to sort itself.

Only part of a vector

The two iterators can mark any range, not only the whole vector. p.begin() + 1 marks place 1, and p.begin() + 5 marks place 5, which is left out. So this call sorts places 1 to 4 and touches nothing else.

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

int main() {
    vector<int> p{5, 1, 4, 2, 3, 9, 0};
    sort(p.begin() + 1, p.begin() + 5);
    cout << "places 1 to 4 sorted:";
    for (int x : p) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

places 1 to 4 sorted: 5 1 2 3 4 9 0

1, 4, 2 and 3 became 1 2 3 4. The 5 in front and the 9 and 0 behind stayed put. Bob, in a hurry, wrote p.begin() + 4 for "up to place 4", and place 4 stayed unsorted. So the second iterator always names the first place that is not sorted.

Your own rule: a first lambda

The third argument of sort is the rule. Here the rule is "a comes before b when a is closer to zero". It is written as a lambda, a small function with no name, written right where it is used.

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

int main() {
    vector<int> d{-7, 3, -1, 5, -4};
    sort(d.begin(), d.end(), [](int a, int b) { return abs(a) < abs(b); });
    cout << "closest to zero first:";
    for (int x : d) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

closest to zero first: -1 3 -4 5 -7

Read [](int a, int b) { return abs(a) < abs(b); } as the answer to sort's one question. Every time sort asks "must a come before b?", the lambda compares the distances from zero. abs, from <cstdlib>, drops the minus sign. Lesson 02 takes the lambda apart piece by piece. So the rule decides the order, and sort itself never changes.

Ties, and what stable_sort adds

Two items are a tie when the rule says neither comes before the other. Amara's shelf holds six books, each with a price and a shelf letter, A to F. Sorted by price, three books cost 30 and two cost 20. stable_sort promises that tied items keep their old order. Plain sort promises nothing about them.

struct Book {
    int price;
    char shelf;
};

bool byPrice(const Book& a, const Book& b) {
    return a.price < b.price;
}

stable_sort(books.begin(), books.end(), byPrice);

byPrice is a comparator written as an ordinary named function. It compares the prices and never looks at the letters. Example 3 below runs it whole, and the widget replays it on GCC 12.

GCC 12 sorted each half of three books, then merged the halves. When two prices were equal, the merge took the book from the left half first. So B stayed ahead of E, and A, C and F stayed in a row. So "stable" means exactly this: tied items come out in the order they went in.

Never count on sort to keep ties

On small inputs, GCC 12's plain sort happens to keep ties. With 16 items or fewer it is one insertion sort, which never moves an item past an equal one. From 17 items, a step that splits the items around one value runs first, and tied items can swap. This program gives records the marks 60, 70 and 80, with the letters a, b, c and so on in input order.

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

struct Rec {
    int mark;
    char tag;
};

bool byMark(const Rec& a, const Rec& b) {
    return a.mark < b.mark;
}

void show(int n, const char* label, const vector<Rec>& v) {
    cout << n << ' ' << label;
    for (const Rec& r : v) {
        cout << ' ' << r.mark << r.tag;
    }
    cout << '\n';
}

int main() {
    for (int n : {16, 17}) {
        vector<Rec> v;
        for (int i = 0; i < n; i++) {
            v.push_back({60 + ((i * 5 + 1) % 3) * 10, char('a' + i)});
        }
        vector<Rec> s = v;
        vector<Rec> t = v;
        sort(s.begin(), s.end(), byMark);
        stable_sort(t.begin(), t.end(), byMark);
        show(n, "sort:       ", s);
        show(n, "stable_sort:", t);
    }
    return 0;
}

16 sort:        60b 60e 60h 60k 60n 70a 70d 70g 70j 70m 70p 80c 80f 80i 80l 80o
16 stable_sort: 60b 60e 60h 60k 60n 70a 70d 70g 70j 70m 70p 80c 80f 80i 80l 80o
17 sort:        60b 60q 60n 60k 60h 60e 70g 70j 70d 70m 70p 70a 80f 80i 80l 80c 80o
17 stable_sort: 60b 60e 60h 60k 60n 60q 70a 70d 70g 70j 70m 70p 80c 80f 80i 80l 80o

With 16 records, the two lines agree. With 17, sort put 60q second and 70a last of the 70s, while stable_sort kept every tie in letter order. Zara tests with 17 or more equal keys first, for exactly this reason. So when ties must keep their order, say so with stable_sort: a test with a few items will not show the difference.

What sorting costs: O(n log n)

Kenji's insertion sort slides each new item past every bigger item before it. On random numbers that is about n²/4 moves, so ten times more items cost about a hundred times more time. std::sort needs about n log₂ n comparisons, where log₂ n is how many times n can be halved: about 17 for 100,000. That is written O(n log n). Since C++11, the standard requires it even in the worst case. Here are Kenji's numbers from eight runs on Compiler Explorer, GCC 12.

At 100,000 items the hand-written sort took over 150 times as long. One more run, the first, took 2,432 ms by hand, which is why the measurement was repeated. stable_sort also costs O(n log n) when it can borrow memory for a buffer, and lesson 02 gives its numbers. So for a big vector the plan matters more than the machine: pick std::sort, and let it ask its questions.

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

int main() {
    vector<int> prices{120, 45, 300, 45, 80};
    sort(prices.begin(), prices.end());
    cout << "low to high:";
    for (int p : prices) {
        cout << ' ' << p;
    }
    cout << '\n';

    sort(prices.begin(), prices.end(), greater<int>());
    cout << "high to low:";
    for (int p : prices) {
        cout << ' ' << p;
    }
    cout << '\n';
    return 0;
}

low to high: 45 45 80 120 300
high to low: 300 120 80 45 45

#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void show(const char* label, const vector<string>& names) {
    cout << label;
    for (const string& name : names) {
        cout << ' ' << name;
    }
    cout << '\n';
}

int main() {
    vector<string> names{"maria", "Zara", "bob", "Amara", "kenji"};
    sort(names.begin(), names.end());
    show("as typed:  ", names);

    for (string& name : names) {
        for (char& c : name) {
            c = tolower(c);
        }
    }
    sort(names.begin(), names.end());
    show("lowercase: ", names);
    return 0;
}

as typed:   Amara Zara bob kenji maria
lowercase:  amara bob kenji maria zara

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

struct Book {
    int price;
    char shelf;
};

bool byPrice(const Book& a, const Book& b) {
    return a.price < b.price;
}

int main() {
    vector<Book> books{{30, 'A'}, {20, 'B'}, {30, 'C'}, {10, 'D'}, {20, 'E'}, {30, 'F'}};
    stable_sort(books.begin(), books.end(), byPrice);
    for (const Book& b : books) {
        cout << b.price << ' ' << b.shelf << '\n';
    }
    return 0;
}

10 D
20 B
20 E
30 A
30 C
30 F

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

void topThree(vector<int> scores) {
    sort(scores.begin(), scores.end(), greater<int>());
    int shown = min(3, (int)scores.size());
    cout << "top " << shown << ':';
    for (int i = 0; i < shown; i++) {
        cout << ' ' << scores[i];
    }
    cout << '\n';
}

int main() {
    topThree({70, 95, 60, 95, 88, 40});
    topThree({50, 75});
    return 0;
}

top 3: 95 95 88
top 2: 75 50

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

int main() {
    vector<int> v{3, 1, 2};
    sort(v.begin(), v.end());
    return 0;
}

vector<int> v{3, 1, 2};
sort(v.begin(), v.end);

vector<int> v{3, 1, 2};
sort(v.begin(), v.end(), greater<int>);

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

struct Student {
    string name;
    int mark;
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    vector<Student> roll(n);   // in roll order, the order the papers were marked
    for (Student& s : roll) {
        cin >> s.name >> s.mark;
    }

    // Put roll in board order: the highest mark first, and students
    // with equal marks in roll order. Then print one student per line.

    return 0;
}

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> score(n);
    for (int& s : score) {
        cin >> s;
    }

    // Drop the k lowest and the k highest scores, and print the sum of
    // the scores that are left.

    return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> height(n);
    for (int& h : height) {
        cin >> h;
    }

    // Print sorted if the shelf is already in order. Otherwise find the
    // first and the last place that differ from the sorted order. Print
    // yes and those two places, counted from 1, if reversing that part
    // sorts the shelf, and no if it does not.

    return 0;
}

Next, lesson 02 goes through every sorting call and every way to write the rule, each with its cost.