In this problem, your goal is to merge a list of K arrays of integers that are already sorted. For example, consider the following three arrays:

arr1 = array.array('i',[1,3,7,11]) arr2 = array.array('i',[2,4,13]) arr3 = array.array('i',[5,6,8])

A possible input with k=3 would the the following list:

input = [arr1,arr2,arr3]

You need to devise and implement an algorithm that will return a single sorted array containing all the values from all 3 arrays. In this example, the ouput would be:

output = array.array('i', [1, 2, 3, 4, 5, 6, 7, 8, 11, 13])

Of course, a simple solution would be to combine all these arrays into one and sort it. This could look like:

def naiveMultimerge(arrs): n = sum(map(len,arrs)) result = array.array('i', bytearray(4*n)) idx = 0 for arr in arrs: for v in arr: result[idx] = v idx += 1 return sorted(result)

naiveMultimerge(input)

Output:

[1, 2, 3, 4, 5, 6, 7, 8, 11, 13]

If n is the sum of the length of all the arrays in the input list, this solution is in O(n log n). We want to do better than this. You could think of a nice divide and conquer solution, but instead I want you to practice solving algorithmic problems with the help of a data structure. You should devise an algorithm that works in O(n log k) where k is the number of arrays in the input list. You should start by defining and implementing your data type.

**Problem:** Devise and implement an algorithm that solves the multimerge problem in O(n log k).

def multimerge(arrs): pass