Sorting in Real Life: std::sort and Comparators

Just use std::sort

std::sort from <algorithm> is a fast, well-tested O(n log n) sort (a mix of quick sort, heap sort and insertion sort called introsort).

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

int main() {
    vector<int> v = {5, 2, 9, 1};
    sort(v.begin(), v.end());
    for (int x : v) cout << x << ' ';
    cout << endl;
    sort(v.begin(), v.end(), greater<int>());     // biggest first
    for (int x : v) cout << x << ' ';
    cout << endl;
    return 0;
}

Output

1 2 5 9 
9 5 2 1 

Sorting your own data with a comparator

A comparator answers “should a come before b?”:

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

struct Student {
    string name;
    int marks;
};

int main() {
    vector<Student> s = {{"Asha", 91}, {"Ravi", 78}, {"Meera", 91}, {"Arjun", 85}};
    sort(s.begin(), s.end(), [](const Student& a, const Student& b) {
        if (a.marks != b.marks) return a.marks > b.marks;   // marks high -> low
        return a.name < b.name;                             // then name A -> Z
    });
    for (auto& st : s) cout << st.name << " " << st.marks << endl;
    return 0;
}

Output

Asha 91
Meera 91
Arjun 85
Ravi 78

Stable sorting

A stable sort keeps tied items in their original order. std::sort is not stable; use stable_sort when that matters.

Common mistake: A comparator must say “strictly before”: use < or >, never <=. Returning true for equal items can make sort misbehave or crash.