Sorting Algorithms

Concept

Sorting arranges elements in order. In contests, use sort() (introsort, O(n log n)) for almost everything. Use stable_sort() when equal elements must keep their original order. Understanding merge sort and quick sort internals helps with problems like counting inversions or custom partitioning.

When to Use

  • ▸sort() — default choice, fastest general-purpose sort
  • ▸stable_sort() — when relative order of equal elements matters
  • ▸Merge sort — counting inversions, external sorting
  • ▸Quick sort — understanding partitioning, quickselect for k-th element
  • ▸Custom comparator — sorting by multiple criteria

Intuition

sort() in C++ uses introsort (hybrid of quicksort + heapsort + insertion sort) and is almost always the right choice. For custom ordering, pass a comparator function. Merge sort is stable and good for counting inversions (count how many times a smaller element from the right half goes before a larger element from the left half during merge). Quick sort partitions around a pivot — elements smaller go left, larger go right — then recurses on each side.

Complexity

Time
O(n log n) for merge sort, quick sort average, and sort()
Space
O(n) merge sort, O(log n) quick sort

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

// --- Merge Sort ---
void merge(vector<int> &v, int l, int mid, int r){
    vector<int> tmp;
    int i = l, j = mid+1;

    while(i <= mid && j <= r){
        if(v[i] <= v[j]) tmp.push_back(v[i++]);
        else tmp.push_back(v[j++]);
    }

    while(i <= mid) tmp.push_back(v[i++]);
    while(j <= r) tmp.push_back(v[j++]);

    for(int i = l; i <= r; i++){
        v[i] = tmp[i-l];
    }
}

void mergeSort(vector<int> &v, int l, int r){
    if(l >= r) return;
    int mid = l + (r - l)/2;
    mergeSort(v, l, mid);
    mergeSort(v, mid+1, r);
    merge(v, l, mid, r);
}

// --- Quick Sort ---
int partition(vector<int> &v, int l, int r){
    int pivot = v[r];
    int i = l;
    for(int j = l; j < r; j++){
        if(v[j] < pivot){
            swap(v[i], v[j]);
            i++;
        }
    }
    swap(v[i], v[r]);
    return i;
}

void quickSort(vector<int> &v, int l, int r){
    if(l >= r) return;
    int p = partition(v, l, r);
    quickSort(v, l, p-1);
    quickSort(v, p+1, r);
}

// --- Custom Comparator ---
bool cmp(pair<int, int> a, pair<int, int> b){
    if(a.first == b.first) return a.second > b.second;
    return a.first < b.first;
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n;
    cin >> n;

    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];

    // Use STL sort (fastest, preferred in contests)
    sort(v.begin(), v.end());

    // Descending order
    // sort(v.begin(), v.end(), greater<int>());

    // Stable sort (keeps relative order of equal elements)
    // stable_sort(v.begin(), v.end());

    // Custom comparator for pairs
    // vector<pair<int, int>> ev;
    // sort(ev.begin(), ev.end(), cmp);

    for(int i = 0; i < n; i++) cout << v[i] << " ";
    cout << "\n";

    return 0;
}

// Sample Input:
// 8
// 5 2 8 1 9 3 7 4
//
// Sample Output:
// 1 2 3 4 5 7 8 9