Merging partially sorted arrays into one array

Problem

  Given three arrays of integers, each of which is sorted, write the program that merges three arrays into one keeping the integers sorted.

 Example inputs:

  arr1 = {3,7,9,15,35};

  arr2 = {2,8,45,60,70,100};

  arr3 = {5,6,50,101, 110};

Answer

Given the fact the integers within each array are already sorted, we can use the Merge step of the merge sort where two arrays with partially sorted integers are merged into one array.

The running time of this merge operation is $O(N)$.

We can run two merge operations: one with arr1, and arr2 and the other with merged(arr1+arr2) array and arr3.

Overall running time will be still $O(N)$.

Here is the complete code.

Practice statistics:

25:00: to write up the code (1 typo, 1 logical flaw)

UPDATE(2022-06-14): Solved the question in python. Instead of executing the merge step repeatedly, I used the K-way merge way, which is a little more complicated due to the implementation of MinHeap.

Basically, we use the min heap to keep the values from three arrays in sorted order. Adding a new element is $log(3)$ since we only keep three elements at most. Overall running time is still $O(N)$

20:00: to write up the minHeap

06:01: to write the main algorithm with flaws. Had a bug in minHeap.