Perform an External Merge Sort with a Heap

External Merge Sort Simulation

External sorting is used when the data to be sorted does not fit into main memory. The algorithm works in two phases:

1. Run Generation: Read chunks of data of at most run_size elements, sort each chunk in memory, and produce sorted runs (simulating temporary disk files).
2. K-Way Merge: Merge the $K$ sorted runs into a single sorted stream using a min-heap.

Implement the function external_sort(stream: Iterable[int], run_size: int) -> Iterator[int].

Requirements

• Chunking: Read elements sequentially from stream. Divide them into runs of length up to run_size. Each run must be sorted in ascending order.
• Merging: Merge the runs using a min-heap of size at most $K$ (where $K$ is the number of runs). To ensure deterministic behavior and stability, break ties between identical values using the run's original index.
• Generator Output: The function must yield elements one by one, simulating streaming output to disk or standard output.
• Input Validation: Raise a ValueError if `run_size Iterator[int]: """ Sorts the input stream using external merge sort with the specified run size. Yields elements in non-decreasing order. """ pass

### Constraints
- `run_size >= 1`
- Total elements `N`: `0 <= N <= 10^6` (for memory testing)
- Element values: `-10^9 <= val <= 10^9`
- Preserves all duplicates

### Examples

**Example 1:**
```python
stream = [7, 1, 5, 2, 9, 3, 4]
run_size = 3
list(external_sort(stream, run_size))
# Output: [1, 2, 3, 4, 5, 7, 9]

Explanation:

• Run 0: [7, 1, 5] -> sorted: [1, 5, 7]
• Run 1: [2, 9, 3] -> sorted: [2, 3, 9]
• Run 2: [4] -> sorted: [4]
• Merging [1, 5, 7], [2, 3, 9], and [4] via min-heap yields [1, 2, 3, 4, 5, 7, 9].

Example 2:

stream = [5, -2, 5, -2]
run_size = 2
list(external_sort(stream, run_size))
# Output: [-2, -2, 5, 5]

Explanation:

• Run 0: [-2, 5]
• Run 1: [-2, 5]
• Merging produces duplicate values in stable order: [-2, -2, 5, 5].

Edge Cases

• Empty stream: should yield nothing.
• run_size greater than the total number of elements: produces a single run, directly yielding sorted elements.
• Stream containing all identical values or already sorted values.