# Perform an External Merge Sort with a Heap Sort an integer sequence using the two phases of external merge sort: create sorted runs that fit within a memory limit, then merge those runs with a min-heap. The literal list below simulates records that would normally be read from and written to external storage. ```python def external_merge_sort(values: list[int], run_capacity: int) -> list[int]: ... ``` Split `values` into consecutive chunks containing at most `run_capacity` items, sort each chunk in ascending order, and perform a k-way heap merge of the resulting runs. Return all values in nondecreasing order. Preserve duplicates. ## Example ```text Input: values = [9, 1, 4, 1, 7, 3, 2] run_capacity = 3 Initial sorted runs: [1, 4, 9], [1, 3, 7], [2] Output: [1, 1, 2, 3, 4, 7, 9] ``` ## Deterministic Heap Rule Store heap entries as `(value, run_index, offset)`. Compare entries in that tuple order. The tie rule does not change integer output, but it makes every merge step deterministic and generalizes to records with stable provenance. ## Constraints and Errors - `0 <= len(values) <= 500_000` - `-10**18 <= values[i] <= 10**18` - `1 <= run_capacity <= 100_000` - A non-integer value or capacity, including a Boolean, or a capacity outside the allowed range raises `ValueError`. - Validate all inputs before constructing runs. - Do not mutate `values`. ## Hints - At most one current element from each nonempty run needs to be in the heap. - After popping an entry, push the next item from the same run. - Explain how the literal runs would become temporary files and buffered readers for data larger than memory. - The merge phase uses `O(number_of_runs)` heap space and `O(n log number_of_runs)` comparisons.