Sorting + Scanning — Use sorting + scanning patterns (intro) - C Plus Plus

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.

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)`

Common problem families solved by sorting + scanning

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

1
Step 1 — Sort the Array

Call 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}
2
Step 2 — Initialize Two Pointers

Set 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
3
Step 3 — Scan: Iteration 1

Compute 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
4
Step 4 — Scan: Iteration 2

sum = 1 + 11 = 12 > 9. Still too large. Decrement hi to 3. Now hi points at 8.

sum = 12 > 9 → decrement hi
5
Step 5 — Scan: Iteration 3

sum = 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.

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

Sort + Scan vs. Hash Map approaches

⚖️

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.

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

From introductory sort + scan to advanced algorithmic techniques

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

Question 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?

Show answer

In a sorted array a[0] ≤ a[1] ≤ … ≤ a[n−1], for any indices i < j < k, we have a[k] − a[i] ≥ a[j] − a[i] and a[k] − a[i] ≥ a[k] − a[j]. Therefore the difference between non-adjacent elements is always greater than or equal to the difference between at least one adjacent pair that lies between them. By induction, the global minimum difference must be realized by some adjacent pair. In an unsorted array, 'adjacent' in the index sense has no relationship to value proximity — elements with the smallest value difference could be anywhere in the array. Sorting creates a bijection between index proximity and value proximity, which is precisely the invariant the scan exploits.

Question 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.

Show answer

First, sort the array: {1, 3, 4, 7, 9, 12}. Now compute adjacent differences: |3−1| = 2, |4−3| = 1, |7−4| = 3, |9−7| = 2, |12−9| = 3. The minimum adjacent difference is 1, occurring between elements 3 and 4. The total work is O(6 log 6) ≈ 16 operations for the sort plus 5 comparisons for the scan. A brute-force approach would require C(6,2) = 15 pair comparisons.

Question 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?

Show answer

Sort the array first. For each index i from 0 to n−3, set lo = i + 1 and hi = n − 1. While lo < hi, compute s = nums[i] + nums[lo] + nums[hi]. If s == 0, return true. If s < 0, increment lo. If s > 0, decrement hi. If no triple is found after all iterations, return false. To avoid duplicates, skip repeated values of nums[i] using a check like 'if (i > 0 && nums[i] == nums[i−1]) continue;'. The time complexity is O(n log n) for the sort plus O(n²) for the outer loop × inner two-pointer scan, yielding O(n²) overall — a significant improvement over the O(n³) brute-force approach.

Question 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.

Show answer

Sort the intervals by their start times. Initialize a result vector with the first interval. Scan from the second interval onward: if the current interval's start is less than or equal to the end of the last interval in the result (overlap detected), merge them by updating the end of the last result interval to max(result.back().end, current.end). Otherwise, push the current interval into the result as a new non-overlapping segment. The sort key is the start time because it ensures that once we pass beyond an interval's start, all future intervals begin at or after that point — any overlap must involve the most recently added result interval. Time: O(n log n) for sort + O(n) for the merge scan = O(n log n). Space: O(n) for the result vector.

Question 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.

Show answer

To preserve indices, create a vector of pairs (value, originalIndex), sort by value, and apply the two-pointer scan on the values. When a matching pair is found, extract the original indices from the pair objects. This uses O(n) extra space for the pair vector. The hash map approach (std::unordered_map) achieves O(n) average time but has O(n²) worst-case due to hash collisions, and its cache performance is poor due to pointer chasing. In a real-time system where worst-case latency is critical — such as trading systems or embedded controllers — the sort + scan approach is preferable because Introsort guarantees O(n log n) worst-case with excellent cache locality (sequential array access). The hash map's amortized O(1) lookups are faster on average but offer no worst-case guarantees. Therefore, sort + scan with index pairs is the more robust choice when deterministic performance bounds are required, despite its marginally higher average-case complexity.

SUMMARY

Summary — Sorting + Scanning Patterns

Summary

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.