Implement the function multimerge(list_of_lists), which is given a list of sorted lists, and returns the multi-way sorted merge of all their elements. To do this, complete and submit the file [login to view URL] on Gradescope.
Multimerge merges h sorted arrays, which contain a total of n elements between them. Your algorithm's complexity must be less than O(n log n), it cannot use more than O(h) additional space, and it cannot use any existing Python "merge" methods (and using "sort" methods will fail the O(n log n) criterion).
This is due 9:59pm Tuesday 19th November.
Examples
multimerge([[-1, 0], [-2]]) ==
[-2, -1, 0]
multimerge([[-2, 0, 4, 5, 6], [1], [-1], [-5, 3, 3, 3, 4], [-3, -1, 4], [-6, 0, 3, 3]]) ==
[-6, -5, -3, -2, -1, -1, 0, 0, 1, 3, 3, 3, 3, 3, 4, 4, 4, 5, 6]
multimerge([[-4, 0, 0], [-5, 4], [-2, 1, 4], [-4, 0, 2, 3, 3], [-5, 1, 3]]) ==
[-5, -5, -4, -4, -2, 0, 0, 0, 1, 1, 2, 3, 3, 3, 4, 4]
multimerge([[-3, -2], [2], [-2, -1], [-5, -3, 2], [-1]]) ==
[-5, -3, -3, -2, -2, -1, -1, 2, 2]
multimerge([[-3, -1, 4], [-2, 3], [-3, 0], [-4, -2, 4]]) ==
[-4, -3, -3, -2, -2, -1, 0, 3, 4, 4]