External Merge Sort with a Heap

Problem: External Merge Sort with a Heap You need to sort a sequence of integers that cannot fit entirely into memory. You are given: n: the number of integers m: the maximum number of integers that can be held in memory at once Then n integers follow Simulate external merge sort: Read at most m integers at a time to form a chunk. Sort each chunk in memory, producing multiple sorted runs. Use a min-heap to perform a k-way merge over all sorted runs and output the final sorted sequence. Input Format n m x1 x2 x3 ... xn The integers may span multiple lines. Output Format Print the sorted n integers separated by spaces. Constraints 0 <= n <= 200000 1 <= m <= max(1, n) -10^9 <= xi <= 10^9 Example Input: 8 3 5 1 9 2 8 3 7 4 Output: 1 2 3 4 5 7 8 9 Example Input 8 3 5 1 9 2 8 3 7 4 Output 1 2 3 4 5 7 8 9