Sorting + Scanning — Use sorting + scanning patterns...

SECTION 1

Historical Context & Motivation

The idea of arranging data before processing it is as old as computing itself. Before electronic computers, librarians, census workers, and mathematicians understood that sorted data could be queried far more efficiently than unsorted collections. When early computer scientists formalized algorithms in the mid-twentieth century, sorting emerged as one of the most studied operations precisely because it unlocked faster downstream processing — the pattern we now call sorting + scanning. This two-phase approach — first sort, then traverse — remains one of the most versatile algorithmic strategies taught in competitive programming, systems design, and software engineering interviews.

1945

Merge Sort Conceived

John von Neumann describes the merge sort algorithm, establishing O(n log n) comparison-based sorting as theoretically optimal and laying the groundwork for sort-then-process paradigms.

1962

Quicksort Published

Tony Hoare publishes Quicksort, which becomes the practical default for in-memory sorting. Its average-case O(n log n) performance makes the sort-first strategy viable for large datasets.

1998

C++ STL sort() Standardized

The ISO C++ Standard formalizes std::sort with guaranteed O(n log n) worst-case (via Introsort), giving C++ programmers a reliable, high-performance sorting primitive out of the box.

2010s

Competitive Programming Boom

Platforms like Codeforces, LeetCode, and HackerRank popularize 'sort + scan' as a named pattern. Hundreds of classic problems — two-sum variants, interval merging, closest-pair queries — are solved by sorting first and scanning linearly.

The central question this pattern addresses is deceptively simple: given an unsorted collection and a query that would normally require checking all pairs (or subsets), can we reduce the work by imposing order first? The answer, as we will see, is a resounding yes — and the cost of sorting (O(n log n)) is almost always dwarfed by the savings it enables.

SECTION 2

Core Principles & Definitions

The sorting + scanning pattern decomposes a problem into two phases. In the sorting phase, we arrange the input according to a chosen key so that related elements become adjacent or ordered. In the scanning phase, we traverse the sorted data — often with a single pass or two-pointer technique — exploiting the invariant that elements to the left are smaller (or equal) and elements to the right are larger. This invariant eliminates redundant comparisons that a brute-force approach would require.

Sort to Impose Order

Use std::sort or a custom comparator to arrange elements by the key most relevant to the query. This step costs O(n log n) but pays dividends by enabling linear-time scans.

Scan with Invariants

Traverse the sorted array maintaining a loop invariant — such as 'the best candidate seen so far' or 'the window boundaries' — that lets you make decisions in O(1) per element.

Two-Pointer Technique

Place one pointer at the start and another at the end (or both at the start). Move them inward or forward based on sorted order, collapsing an O(n²) search to O(n).

Adjacent-Element Reasoning

In a sorted array, the minimum difference between any two elements must occur between adjacent elements. Many optimization problems reduce to comparing neighbors after sorting.

Complexity Trade-off

The total time is O(n log n + n) = O(n log n), dominated by the sort. This is a massive improvement over the O(n²) or O(n³) brute-force alternatives for pair/triple queries.

✦ KEY TAKEAWAY

Think of sorting + scanning like organizing a bookshelf before looking for a specific title. If your books are in random order, you might need to check every single one (O(n) per query, O(n²) for all pairs). But once you sort them alphabetically, you can find any book — or detect duplicates, gaps, and clusters — by simply walking along the shelf in a single pass. The upfront cost of organizing is quickly recovered by the speed of every subsequent lookup.

SECTION 3

Visual Explanation — The Sort + Scan Pipeline

Left: the three-phase pipeline — raw input is sorted, then scanned linearly for the answer (here, the minimum adjacent difference). Right: a complexity comparison showing that the O(n) scan is dominated by the O(n log n) sort, yielding a massive improvement over O(n²) brute force.

The diagram illustrates the fundamental insight: once the array is sorted, neighboring elements are the natural candidates for minimum-difference queries, duplicate detection, and gap analysis. The scan pointer moves left to right exactly once, never backtracking, because the sorted order guarantees that any element to the left of the current position has already been considered. This monotonic traversal property is what makes the scan O(n). The total cost, O(n log n) + O(n), is dominated by the sort — the scan is effectively 'free' in asymptotic terms.

SECTION 4

How It Works — Algorithmic Mechanics in C++

In C++, the sort + scan pattern leans heavily on the Standard Library. The function std::sort(begin, end) uses Introsort (a hybrid of Quicksort, Heapsort, and Insertion Sort) to achieve worst-case O(n log n). Once sorted, the scan phase typically uses a simple for loop or a two-pointer setup. Understanding the mechanics requires formalizing the complexity bounds and the invariants maintained during each phase.

TOTAL TIME COMPLEXITY

T(n) = T_sort(n) + T_scan(n) = O(n log n) + O(n) = O(n log n)

Where n is the number of elements. The scan term is absorbed by the dominant sort term.

BRUTE-FORCE COMPARISON (ALL PAIRS)

T_brute(n) = n × (n − 1) / 2 = O(n²)

Checking all pairs requires C(n, 2) comparisons. For n = 10⁶, this is ≈ 5 × 10¹¹ operations — far too slow.

SPACE COMPLEXITY

S(n) = O(log n) (in-place sort) or O(n) (if copying input)

std::sort operates in-place with O(log n) stack space. If the problem requires preserving original indices, store (value, index) pairs and sort those — costing O(n) extra space.

The Two-Pointer Variant

A particularly powerful scan technique is the two-pointer method. After sorting, place pointer lo at index 0 and pointer hi at index n − 1. If the sum of elements at these pointers is less than a target, increment lo (to increase the sum); if greater, decrement hi (to decrease it). Each pointer moves at most n times, so the scan is O(n). Combined with sorting, the classic two-sum problem is solved in O(n log n) time.

💡 Custom Comparators in C++

Many problems require sorting by a non-default key. Use a lambda: std::sort(v.begin(), v.end(), [](const auto& a, const auto& b){ return a.second < b.second; }); This sorts a vector of pairs by the second element. Choosing the right sort key is often the crux of the problem.

SECTION 5

Problem Classification — When to Reach for Sort + Scan

Not every problem benefits from sorting. The pattern is most effective when the query involves relationships between elements — pairs, neighbors, intervals, or order statistics. Below is a classification of the most common problem families that yield to the sort + scan approach, along with the specific scan technique each family typically employs.

A taxonomy of sort + scan problem families. The three major branches — Pair Queries, Neighbor Queries, and Interval Queries — each employ a different scan strategy but share the same O(n log n) sorting phase. Leaf nodes show specific classic problems.

Common problem families solved by sorting + scanning

Problem Family	Sort Key	Scan Technique	Typical Complexity
Two-Sum / k-Sum	Element value	Two-pointer (lo/hi)	`O(n log n)`
Minimum Difference	Element value	Adjacent comparison	`O(n log n)`
Duplicate Detection	Element value	Adjacent equality check	`O(n log n)`
Merge Intervals	Start time	Greedy merge sweep	`O(n log n)`
Activity Selection	End time	Greedy pick next	`O(n log n)`

SECTION 6

Worked Example — Two-Sum via Sort + Scan

Consider the following problem: given an integer array nums = {2, 7, 11, 15, 1, 8} and a target T = 9, find whether any two distinct elements sum to T. A brute-force nested loop would check all 15 pairs in O(n²). We will solve it in O(n log n) using sort + scan with two pointers.

Two-Sum with Sort + Two-Pointer Scan

Step 1 — Sort the ArrayCall std::sort on the array. The sorted result is {1, 2, 7, 8, 11, 15}. This step costs O(n log n) = O(6 × log₂ 6) ≈ O(6 × 2.58) ≈ 16 operations.

Sorted: {1, 2, 7, 8, 11, 15}

Step 2 — Initialize Two PointersSet lo = 0 (pointing at 1) and hi = 5 (pointing at 15). The invariant is: if a valid pair exists, it lies within the range [lo, hi].

lo → 1, hi → 15

Step 3 — Scan: Iteration 1Compute sum = a[lo] + a[hi] = 1 + 15 = 16. Since 16 > 9 (target), the sum is too large. Decrement hi to 4. Now hi points at 11.

sum = 16 > 9 → decrement hi

Step 4 — Scan: Iteration 2sum = 1 + 11 = 12 > 9. Still too large. Decrement hi to 3. Now hi points at 8.

sum = 12 > 9 → decrement hi

Step 5 — Scan: Iteration 3sum = 1 + 8 = 9 == 9. Match found! The pair (1, 8) sums to the target. The scan performed only 3 iterations instead of 15 brute-force comparisons.

✓ Found pair (1, 8) with sum = 9

⌨️ C++ Implementation

A concise C++ solution:

bool twoSum(vector<int>& nums, int T) { sort(nums.begin(), nums.end()); int lo = 0, hi = (int)nums.size() - 1; while (lo < hi) { int s = nums[lo] + nums[hi]; if (s == T) return true; else if (s < T) ++lo; else --hi; } return false; }

SECTION 7

Strengths, Limitations & Trade-offs

Sort + scan is a powerful general-purpose technique, but it is not always the optimal choice. Understanding when it excels and when alternatives like hash-based approaches or specialized data structures outperform it is crucial for making informed design decisions in competitive programming and real-world software engineering.

Sort + Scan vs. Hash Map approaches

Dimension	Sort + Scan	Hash Map Alternative
Time Complexity	O(n log n) — deterministic	O(n) average, O(n²) worst-case (hash collisions)
Space Complexity	O(1) extra (in-place sort) or O(n) if index tracking needed	O(n) always (hash table overhead)
Cache Performance	Excellent — sequential memory access in scan phase	Poor — random memory access patterns
Preserves Original Order	No (unless index pairs stored)	Yes
Handles Multiple Queries	Great — sort once, scan many times (amortized)	Must rebuild hash table for structural changes
Best For	Neighbor queries, interval problems, multi-query scenarios	Single exact-match lookups, frequency counting

⚖️ WHEN TO CHOOSE SORT + SCAN

Choose sort + scan when the problem involves relationships between elements — minimum gaps, overlapping intervals, or ordering constraints — where the structure imposed by sorting directly enables the solution. Choose hash-based approaches when you need constant-time single-element lookups and the problem doesn't benefit from global order. In practice, many competitive programmers default to sort + scan because its worst-case is guaranteed O(n log n) with no hash collision risk, and it tends to have superior cache locality.

SECTION 8

Connections to Advanced Techniques

The sort + scan pattern is the entry point to a family of increasingly sophisticated algorithmic techniques. Once you are comfortable with the basic two-phase approach, you can extend it to handle more complex constraints and higher-dimensional problems. Understanding these connections helps you recognize when a problem is a disguised variant of sort + scan — or when you need to reach for a more powerful tool.

From introductory sort + scan to advanced algorithmic techniques

Introductory (This Lesson)	Advanced Extension
Sort array + two-pointer scan	Sort + binary search (for non-linear scan targets)
Adjacent-element comparison	Sweep line algorithms (2D interval/event problems)
Sort by one key	Sort by one key + BIT/segment tree for second dimension (e.g., LIS, inversion count)
Greedy interval merge	Interval scheduling with weighted jobs (DP + binary search)
Single-pass scan with accumulator	Sliding window / monotonic deque for range queries

A particularly important extension is the sweep line algorithm, which generalizes the sort + scan idea to two dimensions. Instead of sorting points on a number line, you sort events (such as segment endpoints) and 'sweep' a vertical line across the plane, maintaining an active set of objects. Problems like finding the maximum number of overlapping rectangles or computing the area of a union of rectangles rely on this generalization. Similarly, the Longest Increasing Subsequence problem can be viewed as sorting by one dimension and then applying a patience-sorting scan — a direct descendant of the sort + scan pattern.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

Explain why, in a sorted array, the minimum absolute difference between any two elements must occur between two adjacent elements. Why does this property fail for unsorted arrays?

PROBLEM 2 — BASIC CALCULATION

Given the array {12, 4, 7, 1, 9, 3}, sort it and then scan to find the minimum absolute difference between any two elements. State the pair and the difference.

PROBLEM 3 — INTERMEDIATE

Write a C++ function that takes a vector<int> and returns true if there exist three elements a, b, c (not necessarily distinct indices) such that a + b + c = 0. Use the sort + scan pattern with a two-pointer inner loop. What is the time complexity?

PROBLEM 4 — APPLIED

A server receives n network packets, each described as an interval [start_i, end_i]. Two packets conflict if their intervals overlap. Write a C++ solution using sort + scan to merge all overlapping intervals into a minimal set of non-overlapping intervals. Describe the sort key and the scan logic.

PROBLEM 5 — CRITICAL THINKING

Sort + scan destroys original index information. Suppose a problem asks you to return the original indices of the two elements that sum to a target (like LeetCode's Two Sum). How would you adapt the sort + scan approach to preserve index information? Compare the trade-offs with a hash map solution and argue which is preferable in a real-time system where worst-case latency matters.

SUMMARY

Summary — Sorting + Scanning Patterns

The sorting + scanning pattern is a two-phase algorithmic strategy: first, impose order on the input using std::sort (O(n log n)), then traverse the sorted data with a linear scan (O(n)) that exploits the sorted invariant. This reduces problems that would otherwise require O(n²) brute-force pair checking to O(n log n) total. The scan phase can take several forms: a two-pointer technique for pair-sum queries, an adjacent-element comparison for minimum-gap and duplicate problems, or a greedy merge sweep for interval-based problems.

Key trade-offs to remember: sort + scan offers deterministic O(n log n) worst-case performance and excellent cache locality, but it destroys original index order (recoverable by sorting (value, index) pairs) and may be outperformed by hash-based O(n) solutions for single-element lookups. The pattern scales naturally to advanced techniques including sweep line algorithms, segment trees, and multi-dimensional sorting — making it one of the most foundational problem-solving tools in a C++ programmer's arsenal.