How would you sort 5 million order records by region then signup date in a memory-capped container?

## Turn the ask into requirements Three constraints are on the table: an ordering over two fields, five million records, and a memory ceiling. Each maps to a different decision, and the strongest answers separate them instead of jumping to an algorithm name. **The ordering.** Ordering by region, then by signup date within a region, is a single comparator over the pair. That is worth stating explicitly because of a widespread misconception: multi-field ordering does **not** require a stable sort. Stability preserves the input order of records that compare **equal**, and under a composite comparator two records compare equal only when they match on region *and* signup date. If those full ties must retain arrival order, you have two options: use a stable algorithm, or append a monotonically increasing sequence number as a third key component — after which every record is distinct, ties do not exist, and any algorithm produces the same answer. The tiebreaker route is usually better, because it makes the result reproducible regardless of which sort runs. The alternative technique — sort by signup date, then sort again by region and rely on stability to preserve the date order — *works*, but only with a genuinely stable sort, and it costs two full passes. Prefer the one-pass composite comparator unless the two orderings are computed at different times by different code. **The size.** Five million is comfortably an in-memory problem for records of modest width, and saying so is part of the answer: do not reach for the out-of-core family before checking. Five million records at 200 bytes each is roughly a gigabyte of payload; at 2 kilobytes each it is ten gigabytes and the conversation changes. Ask for record width before deciding. **The ceiling.** This is where the real engineering lives, and the key question is *what the sort moves*. ## Accounting for memory precisely A merge sort over an array of records needs an auxiliary buffer holding n records — that is a second copy of the payload. Two moves shrink it dramatically: 1. **Sort references, not records.** Build an array of n references (or indices) and sort that with a comparator that dereferences. The auxiliary buffer becomes n pointer-sized slots — for 5 million records, tens of megabytes rather than gigabytes — and no record payload is copied. The cost is locality: every comparison chases a reference into scattered memory, so cache misses rise. For small records this is a net loss; for wide records it is a large win. 2. **Extract a sort key.** Build an array of (packed key, index) pairs where the packed key encodes region and signup date in a single comparable value. Comparisons then touch contiguous, cache-resident data and never dereference at all; only the final permutation touches the records. This is the classic key-extraction trick and it usually beats reference sorting on both memory traffic and comparison cost. If the ceiling is tight enough that even the pointer buffer is unwelcome, an in-place O(n log n) sort — heapsort, or a depth-limited partitioning hybrid — uses O(1) or O(log n) auxiliary space. You give up stability and some locality; with a sequence-number tiebreaker in the key, losing stability costs you nothing. ## Exploiting the shape of the key Region is a low-cardinality categorical field: perhaps dozens of distinct values. That invites a **distribution pass**: count records per region in one scan, compute offsets, place each record into its region's segment, then sort each segment by signup date independently. Properties worth naming: - Peak working set is one segment, not the whole dataset — directly useful under a ceiling. - Segments sort independently, so they parallelise with no coordination. - Concatenating segments in region order yields the final order with no merge step. - The risk is **skew**: if one region holds 70% of orders, the largest segment dominates and you have gained little on peak memory. Check the distribution before committing. Signup dates are also structured — a timestamp is a bounded fixed-width integer — so a radix pass over date within a segment is available if comparison cost turns out to dominate. That is a measurement-driven optimisation, not a default. ## The answer, assembled "Composite comparator over (region, signup date), with a sequence number appended if arrival order among full ties matters. Sort an array of extracted (packed key, index) pairs rather than the records themselves — that keeps the auxiliary buffer at pointer scale and the comparisons cache-friendly. If the container ceiling is still tight, distribute by region first and sort each segment by date, which bounds the peak working set to the largest segment; I would check region skew first. I would stay with the standard library sort throughout and only revisit if profiling shows comparison or copy cost dominating." That answer names the requirement, the memory model, the data shape and the escape hatch — which is precisely the judgment being probed.