Sorting Patterns for Competitive Programming

March 2026 · 25 min read

Sorting is rarely the entire solution. It is usually the first step that enables a faster algorithm. This post covers the most important patterns where sorting unlocks an efficient solution: custom comparators, sort combined with two pointers, sort combined with binary search, interval scheduling, and counting inversions with merge sort.

Each pattern includes the key idea, when to recognize it, and complete C++ code.

Pattern 1: Custom Comparators

The default sort orders elements in ascending order. Many problems require a different ordering: sort by second element, sort strings by length, sort events by end time. C++ makes this easy with custom comparators.

Lambda Comparator

// Sort pairs by second element (ascending)
vector<pair<int,int>> v = {{3,5},{1,2},{4,1},{2,8}};
sort(v.begin(), v.end(), [](const pair<int,int>& a, const pair<int,int>& b){
    return a.second < b.second;
});
// Result: {4,1}, {1,2}, {3,5}, {2,8}

Struct with Comparator

struct Event {
    int start, end, id;
};

// Sort by end time, break ties by start time
sort(events.begin(), events.end(), [](const Event& a, const Event& b){
    if (a.end != b.end) return a.end < b.end;
    return a.start < b.start;
});

Common Comparator Pitfalls

Largest Number Problem

Given a list of non-negative integers, arrange them to form the largest number. The trick is a custom comparator that compares string concatenations.

// LeetCode 179: Largest Number
string largestNumber(vector<int>& nums) {
    vector<string> strs;
    for (int x : nums) strs.push_back(to_string(x));

    sort(strs.begin(), strs.end(), [](const string& a, const string& b){
        return a + b > b + a;  // "30" + "3" = "303" vs "3" + "30" = "330"
    });

    if (strs[0] == "0") return "0";
    string result;
    for (const string& s : strs) result += s;
    return result;
}

Sort by Frequency

// Sort elements by frequency (most frequent first), ties broken by value
vector<int> frequencySort(vector<int>& nums) {
    unordered_map<int,int> freq;
    for (int x : nums) freq[x]++;

    sort(nums.begin(), nums.end(), [&freq](int a, int b){
        if (freq[a] != freq[b]) return freq[a] > freq[b];
        return a < b;
    });
    return nums;
}

Pattern 2: Sort + Two Pointers

Many problems ask for pairs or triplets satisfying a condition. Brute force checks all combinations in $O(n^2)$ or $O(n^3)$. Sorting first enables a two-pointer scan that reduces the complexity by one order.

3Sum

Find all unique triplets that sum to zero. After sorting, fix one element and use two pointers on the remaining subarray.

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    int n = nums.size();

    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;  // skip duplicates
        int lo = i + 1, hi = n - 1;
        int target = -nums[i];

        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            if (sum == target) {
                result.push_back({nums[i], nums[lo], nums[hi]});
                while (lo < hi && nums[lo] == nums[lo+1]) lo++;
                while (lo < hi && nums[hi] == nums[hi-1]) hi--;
                lo++; hi--;
            } else if (sum < target) {
                lo++;
            } else {
                hi--;
            }
        }
    }
    return result;
}

Two Sum (Sorted Array)

// LeetCode 167: Two Sum II
vector<int> twoSum(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        if (sum == target) return {lo + 1, hi + 1};
        else if (sum < target) lo++;
        else hi--;
    }
    return {};  // guaranteed to have a solution
}

Closest Pair Sum

// Find two elements whose sum is closest to a target
pair<int,int> closestPairSum(vector<int>& arr, int target) {
    sort(arr.begin(), arr.end());
    int lo = 0, hi = arr.size() - 1;
    int bestDiff = INT_MAX;
    pair<int,int> result;

    while (lo < hi) {
        int sum = arr[lo] + arr[hi];
        if (abs(sum - target) < bestDiff) {
            bestDiff = abs(sum - target);
            result = {arr[lo], arr[hi]};
        }
        if (sum < target) lo++;
        else if (sum > target) hi--;
        else break;  // exact match
    }
    return result;
}

Pattern 3: Sort + Binary Search

When you need to answer "does this value exist?" or "what is the first value >= X?" for many queries, sort once and binary search each query. This reduces per-query time from $O(n)$ to $O(\log n)$.

Counting Pairs with Difference

// Count pairs (i, j) where |arr[i] - arr[j]| == k
int countPairsWithDiff(vector<int>& arr, int k) {
    sort(arr.begin(), arr.end());
    int count = 0;
    for (int i = 0; i < (int)arr.size(); i++) {
        // Search for arr[i] + k in arr[i+1..]
        if (binary_search(arr.begin() + i + 1, arr.end(), arr[i] + k))
            count++;
    }
    return count;
}

Two Arrays: Count Pairs

Given two arrays a[] and b[], for each element in a, count how many elements in b are less than it.

// For each a[i], count elements in b[] that are strictly less
vector<int> countSmaller(vector<int>& a, vector<int>& b) {
    sort(b.begin(), b.end());
    vector<int> result;
    for (int x : a) {
        // lower_bound gives first element >= x
        int cnt = lower_bound(b.begin(), b.end(), x) - b.begin();
        result.push_back(cnt);
    }
    return result;
}

Longest Increasing Subsequence (Patience Sort)

LIS can be solved in $O(n \log n)$ using a sort-like approach with binary search. Maintain a "tails" array where tails[i] is the smallest tail element of all increasing subsequences of length i+1.

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end())
            tails.push_back(x);
        else
            *it = x;
    }
    return tails.size();
}

Pattern 4: Interval Scheduling After Sorting

Interval problems almost always start with sorting. The two most common orderings are: sort by start time (for merging overlapping intervals) and sort by end time (for selecting the most non-overlapping intervals).

Merge Overlapping Intervals

Sort intervals by start time. Then scan left to right, merging whenever the current interval overlaps with the previous one.

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> merged;

    for (auto& iv : intervals) {
        if (merged.empty() || merged.back()[1] < iv[0]) {
            merged.push_back(iv);
        } else {
            merged.back()[1] = max(merged.back()[1], iv[1]);
        }
    }
    return merged;
}

Maximum Non-Overlapping Intervals (Activity Selection)

Sort by end time. Greedily select the interval that ends earliest and does not overlap with the last selected interval. This greedy choice is provably optimal.

int maxNonOverlapping(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){
        return a[1] < b[1];  // sort by end time
    });

    int count = 1, lastEnd = intervals[0][1];
    for (int i = 1; i < (int)intervals.size(); i++) {
        if (intervals[i][0] >= lastEnd) {
            count++;
            lastEnd = intervals[i][1];
        }
    }
    return count;
}

Minimum Meeting Rooms

Sort start times and end times separately. Use two pointers to track how many meetings are active at any point.

int minMeetingRooms(vector<vector<int>>& intervals) {
    vector<int> starts, ends;
    for (auto& iv : intervals) {
        starts.push_back(iv[0]);
        ends.push_back(iv[1]);
    }
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());

    int rooms = 0, maxRooms = 0, e = 0;
    for (int s = 0; s < (int)starts.size(); s++) {
        if (starts[s] < ends[e]) {
            rooms++;
        } else {
            e++;
        }
        maxRooms = max(maxRooms, rooms);
    }
    return maxRooms;
}

Pattern 5: Inversion Count via Merge Sort

An inversion is a pair $(i, j)$ where $i < j$ but $\text{arr}[i] > \text{arr}[j]$. The number of inversions measures how far the array is from being sorted. Counting inversions naively takes $O(n^2)$. Using a modified merge sort, we can count them in $O(n \log n)$.

The Key Insight

During the merge step, when we pick an element from the right half because it is smaller than the current element from the left half, that element forms inversions with all remaining elements in the left half.

If the left half has elements at positions i through mid and we pick right[j] because right[j] < left[i], then right[j] is inverted with left[i], left[i+1], ..., left[mid]. That is mid - i + 1 inversions.

C++ Implementation

long long mergeCount(vector<int>& arr, int left, int mid, int right) {
    vector<int> tmp;
    int i = left, j = mid + 1;
    long long inversions = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            tmp.push_back(arr[i++]);
        } else {
            // arr[j] is smaller than arr[i..mid], so (mid - i + 1) inversions
            inversions += (mid - i + 1);
            tmp.push_back(arr[j++]);
        }
    }
    while (i <= mid)  tmp.push_back(arr[i++]);
    while (j <= right) tmp.push_back(arr[j++]);
    for (int k = left; k <= right; k++)
        arr[k] = tmp[k - left];
    return inversions;
}

long long mergeSortCount(vector<int>& arr, int left, int right) {
    if (left >= right) return 0;
    int mid = left + (right - left) / 2;
    long long inv = 0;
    inv += mergeSortCount(arr, left, mid);
    inv += mergeSortCount(arr, mid + 1, right);
    inv += mergeCount(arr, left, mid, right);
    return inv;
}

long long countInversions(vector<int>& arr) {
    return mergeSortCount(arr, 0, arr.size() - 1);
}

The time complexity is $O(n \log n)$, same as merge sort. The space complexity is $O(n)$ for the temporary array.

Applications of Inversion Count

• Measuring sortedness: 0 inversions means fully sorted. $\frac{n(n-1)}{2}$ inversions means reverse sorted.
• Kendall tau distance: The number of inversions between two rankings. Used in recommendation systems.
• Counting swaps: Bubble sort performs exactly one swap per inversion. The inversion count equals the number of bubble sort swaps.
• LeetCode 493 (Reverse Pairs): Count pairs where arr[i] > 2*arr[j] and i < j. Same merge sort approach with a modified condition.

Pattern Summary

How to Recognize These Patterns

• "Find all pairs/triplets that..." Sort + two pointers.
• "For each element, find the nearest/first..." Sort + binary search.
• "Arrange elements to maximize/minimize..." Custom comparator.
• "Intervals: overlap, merge, select..." Sort by start or end time.
• "How far from sorted?" or "count swaps" Inversion count.
• "Minimize the maximum difference" Sort, then sliding window or binary search on the answer.

Practice Problems

• LeetCode 179: Largest Number (custom comparator)
• LeetCode 15: 3Sum (sort + two pointers)
• LeetCode 16: 3Sum Closest (sort + two pointers)
• LeetCode 167: Two Sum II (sort + two pointers)
• LeetCode 300: Longest Increasing Subsequence (sort + binary search)
• LeetCode 56: Merge Intervals (interval scheduling)
• LeetCode 253: Meeting Rooms II (interval scheduling)
• LeetCode 435: Non-overlapping Intervals (interval scheduling)
• LeetCode 493: Reverse Pairs (inversion count)
• LeetCode 315: Count of Smaller Numbers After Self (inversion count variant)

Summary

• Sorting is the prerequisite step in many competitive programming patterns.
• Custom comparators let you sort by any criterion. Always use strict less-than (<), never <=.
• Sort + two pointers reduces pair/triplet search from $O(n^2)$/$O(n^3)$ to $O(n \log n)$/$O(n^2)$.
• Sort + binary search handles repeated "find in collection" queries efficiently.
• Interval problems: sort by start time to merge, sort by end time to select maximum non-overlapping.
• Inversion count via merge sort runs in $O(n \log n)$ and measures how far an array is from sorted.