Skip to content

Sorting & Comparators

In one sentence

sort puts things in increasing order by default; give it a comparator cmp(x, y) that answers "should x come before y?" and it will put them in any order you can describe.

1. What problem does it solve?

Example — 632C · The Smallest String Concatenation (1-vector_sort · K, rating 1700)

You are given \(n\) lowercase strings. Glue all of them together in some order so that the result is the lexicographically smallest possible string.

Limits: \(n \le 5 \cdot 10^4\), each string has length at most \(50\).

Input          Output
4
abba
abacaba
bcd
er             abacabaabbabcder

3
c
cb
cba            cbacbc

The obvious idea fails. Sort the strings normally and join them: for the second sample that gives c, cb, cba → ccbcba. But cba + cb + c = cbacbc is smaller. Plain dictionary order is the wrong rule here, so we need to write our own rule.

2. The math

2.1 Only neighbours matter

Look at two strings \(x\) and \(y\) that end up next to each other in the answer:

\[ \dots \; x \, y \; \dots \qquad\text{versus}\qquad \dots \; y \, x \; \dots \]

Everything before and after is the same, and \(xy\) and \(yx\) have the same length. So the whole answer is smaller exactly when \(xy < yx\). That gives the rule:

\[ x \text{ comes before } y \iff x + y < y + x . \]

For c and cb: c+cb = ccb, cb+c = cbc, and cbc < ccb, so cb goes first.

2.2 Why sorting with this rule is safe

sort needs the rule to behave like "less than": it must never say both "\(x\) before \(y\)" and "\(y\) before \(x\)", and it must be transitive (if \(x\) before \(y\) and \(y\) before \(z\), then \(x\) before \(z\)). Here is why \(xy < yx\) is transitive.

Treat a string as a number written in base \(26\), and let \(|x|\) be its length. Gluing is then arithmetic: \(xy = x \cdot 26^{|y|} + y\). So

\[ xy < yx \iff x\,(26^{|y|} - 1) < y\,(26^{|x|} - 1) \iff \frac{x}{26^{|x|} - 1} < \frac{y}{26^{|y|} - 1}. \]

Every string gets one fixed score \(\dfrac{x}{26^{|x|}-1}\), and the rule just compares scores. Comparing numbers is transitive, so the rule is too.

(Strings like a compare equal to aa under this rule, which is fine: both orders give the same answer.)

2.3 Why the sorted order is the best order

Take any order and suppose some neighbours are "wrong": \(y\) directly before \(x\) although \(xy < yx\). Swapping them makes the string strictly smaller. Keep swapping wrong neighbours (like bubble sort) until none are left: the string never gets bigger, and what remains is exactly the sorted order. So the sorted order is at least as small as every other order.

2.4 Cost

Sorting does \(O(n \log n)\) comparisons; each builds two strings of length at most \(100\). About \(5\cdot10^4 \cdot 16 \cdot 100 \approx 8\cdot10^7\) character operations, well under the 3-second limit.

3. Lesson notes (1 and 8 February)

Typo in the 8 February recap

In String concatenation the variable is called t, so the last line should read s + " " + t. As written (+ world) it does not compile. The note is kept unchanged below.

Math Symbols

  • \(\forall\) (raw LaTeX code: \forall): The Universal Quantifier.

  • Meaning: "For all" or "For any". Represents that a condition is satisfied by every variable in a specific range.

  • \(\sum\_{i=1}^{n}\) (raw LaTeX code: \sum_{i=1}^{n}): The Summation symbol.

  • Meaning: The sum of a sequence starting from \(i=1\) up to \(i=n\).

STL Functions & Grammar

  • sort(begin, end)

  • Sorts the array/container in the range [begin, end).

  • Note: The range is left-closed, right-open (includes begin, excludes end).

  • Default: Sorts in increasing order.

  • swap(a, b)

  • Swaps the values of any two variables a and b.

  • Requirement: a and b must be of the same type.

  • reverse(begin, end)

  • Reverses the order of elements in the range [begin, end).

Iterator

  • Concept: An object that behaves like a pointer. It is used to traverse containers (like vector, set, etc.).

  • Dereferencing: To get the value an iterator points to, use the * operator (e.g., *it).

  • Example: For a vector v, *v.begin() is equivalent to v.front() (accessing the first element).

Custom Sorting

  • Comparator: We can pass a third parameter to the sort function to define a custom sorting rule.

  • Function Signature: bool cmp(T x, T y)

  • Logic: If the function returns true, then x is placed in front of y.

  • Type T: Represents any data type (int, double, string, struct, vector, etc.).

1. String concatenation

We can concatenate two strings directly using the + operator. E.g. 

std::string s="hello", t="world";
std::string con = s + " " + world;

2. Custom sorting

By defining the custom compare function, we could sort the vector in any order we want. Note: - The cmp function should always have 2 parameters with the same type of the vector to sort. - The cmp function answers the question "Should x come before y?". Here we suppose the two parameters are x and y respectively, and the return boolean value is the answer of the question above.

3. Custom data type

Since class is too OOP in C++, here we only use the C-style structure: struct. Usage: 

struct Point {
    int x, y;
};
Point p;
std::cin >> p.x >> p.y;

4. Worked solution — The Smallest String Concatenation

The comparator is a lambda, written directly inside sort:

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    // x goes before y exactly when x + y is smaller than y + x
    sort(s.begin(), s.end(), [](const string &x, const string &y) {
        return x + y < y + x;
    });

    string ans;
    for (int i = 0; i < n; i++) {
        ans += s[i];
    }
    cout << ans << "\n";
}

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

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

The same shape sorts structs. For example, points by x, and by y when x ties:

struct Point {
    int x, y;
};

bool cmp(Point a, Point b) {
    if (a.x != b.x) {
        return a.x < b.x;
    }
    return a.y < b.y;
}

// sort(p.begin(), p.end(), cmp);

5. Common mistakes

Using <= in a comparator

return a <= b; says "\(x\) before \(x\)" is true. sort requires a strict rule; with <= it may loop forever or crash when there are equal elements. Always use < or >.

A rule that is not transitive

If your rule can say \(a\) before \(b\), \(b\) before \(c\), but \(c\) before \(a\), the result is undefined. When you invent a rule, check it the way §2.2 does, or find a single "score" it compares.

Forgetting that the range is half-open

sort(a.begin(), a.begin() + k) sorts the first k elements, indices \(0 \dots k-1\). With 1-indexed arrays, sort a.begin() + 1, a.begin() + n + 1.

Sorting values when you need positions

If the output must keep the original order (as in AIO 2026 · Mundane Square), sort a vector of indices with a comparator that looks up the values.

6. Practice

Problem Set Rating Idea
1851B · Parity Sort 2-custom_sorting · B 800 sort odds and evens separately, compare with fully sorted
1999C · Showering 2-custom_sorting · A 800 intervals already in order, check the gaps
2036B · Startup 2-custom_sorting · D 800 total per brand, sort decreasing
1927C · Choose the Different Ones! 2-custom_sorting · C 1000 count values only in \(a\), only in \(b\), in both
160A · Twins 1-vector_sort · G 900 sort decreasing, take the largest coins
632C · The Smallest String Concatenation 1-vector_sort · K 1700 comparator \(x+y<y+x\) (this page)
Credits & licenses
  • §3 is the lesson notes from 1 and 8 February, unchanged apart from heading levels (the Big-O part of 8 February is on Complexity & Constraints).
  • The "score" proof of transitivity is the standard argument for this problem; the write-up, example traces, worked solution and mistakes are ours.