Split the points by x, solve each half, then check only the points within δ of the split line — sorted by y, each against at most the next 7. Why 7 is enough: all later strip points that could still be closer than δ lie in a δ × 2δ box above the current one, and that box holds at most 8 points (dashed while the strip is checked). The page runs the same execution in two variants: with the arrays sorted a single time up front and split without re-sorting, or re-sorting in every recursive call from scratch. Watch the comparison count.
Sorting is charged its real comparison count, via a counting merge sort — it is a black box here, not animated stroke by stroke. Distance evaluations (d2, in the base cases and the strip check) are counted separately and are the same for both variants on the same input: they depend only on which points end up compared, not on how the arrays got sorted. The one thing that differs between the two variants is the sorting cost — which is exactly the point.
Sort once pays for two sorts (by x, by y) a single time, in the driver, then only ever splits already-sorted arrays — no further comparisons. Sort every level re-sorts the current subset by x and by y at the start of every recursive call, giving the recurrence T(n) = 2T(n/2) + Θ(n log n) instead of T(n) = 2T(n/2) + Θ(n) — an extra log factor that the recursion-tree method turns into O(n log2 n) overall.
1. The tie-break. Splitting byY by re-testing P[byY[i]].x ≤ m.x can put
more points on the left than byXₗ actually holds whenever two points share x = m.x —
the two arrays would then describe different point sets. Fixed by marking, from byX itself, which
point identities are in the left half, and splitting byY by that mark.
2. for i := 0,…,C.size() reads one past the end of C — every
other loop in this code writes 0,…,n−1; fixed to C.size()−1.
3. for j := i+1,…,i+7 has no bound against C.size(); fixed to
j := i+1,…,min(i+7, C.size()−1).
x y, separated by spaces or commas; lines starting with
# are ignored. Point i is the i-th point line (counting from 0). A first line with a
single number n (as in the algs4 Point2D inputs) is accepted and skipped.
byX. Points with identical coordinates are allowed; they are drawn
slightly apart so both stay visible.