Lesson 14.5 · Sorting and Divide & Conquer

Sorting as a Tool

Sort first, then scan: neighbours become comparable, duplicates sit together, and greedy choices become obvious.

10 min

Think of it like this

Lining people up by arrival time before deciding who gets a seat: once they're in order, every decision only depends on the person in front.

1.What sorting unlocks

Two pointers on sorted values (3Sum), merging overlapping intervals (sort by start), greedy scheduling (sort by end time), grouping equal items (adjacent after sorting), and custom orders like "which concatenation is bigger" (Largest Number).

The cost is O(n log n) and the loss of original positions. If you need positions, sort an array of indexes with a comparator on the values.

SortIndexes.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] price = {300, 120, 250};
        Integer[] idx = {0, 1, 2};
        Arrays.sort(idx, (a, b) -> Integer.compare(price[a], price[b]));   // indexes ordered by price
        System.out.println(Arrays.toString(idx));
    }
}

Output

[1, 2, 0]

Remember

Sort, then scan neighbours.
Sort indexes when original positions matter.
Sorting cost (n log n) is usually cheaper than the O(n²) it replaces.

Common mistakes

Sorting the input when the problem needs original indexes.

Command Palette

Sorting as a Tool

1.What sorting unlocks