← All patterns

Sort and Search

Sorting exposes structure that a linear or binary-search sweep can then exploit. The most versatile 'preprocess then query' pattern — applies whenever pairs, ranges, or extremes matter.

18 problems 5 Easy 8 Medium 5 Hard

Many problems become tractable after sorting, exposing structure that binary search or a two-pointer sweep can exploit. The sort is the preprocessing; the actual answer comes from the linear or O(log n) phase. Total cost is dominated by the sort: O(n log n).

The pattern is the most-versatile preprocessing — pair sums (3Sum, kSum), interval queries, range searches, and 'merge two sorted arrays' problems all start here.

When to reach for this pattern

  • Find pairs / triplets with a property (sum, difference, ratio)
  • Range or interval queries over the input
  • Problem becomes easier if elements are sorted by some key
  • kth smallest, kth largest, or rank-based queries

Canonical template 

sort(nums.begin(), nums.end());

// converging two-pointer after sort
int l = 0, r = nums.size() - 1;
while (l < r) {
    int sum = nums[l] + nums[r];
    if (sum == target) return {l, r};
    if (sum < target) ++l;
    else --r;
}

// binary search for first index >= target
auto it = lower_bound(nums.begin(), nums.end(), target);

C++ · adapt the names and types to your problem.

Common pitfalls

  • Sorting destroys original indices — keep a (value, originalIndex) pair when needed
  • Custom comparator must be a strict weak ordering — non-transitive triggers UB
  • Sorting + linear is O(n log n) but for tiny n a different algorithm may be simpler
  • Stable sort vs unstable: std::sort is unstable; std::stable_sort keeps order on equals

Related patterns

Two Pointers Modified Binary Search Greedy Techniques

Problems (18)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.