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.

	#include<vector>
	#include<iostream>
	using namespace std;
	vector<int> merge(vector<int> left, vector<int> right)
	{
	vector<int> merged;
	int lpos = 0, rpos = 0;
	int len1 = left.size();
	int len2 = right.size();
	while(lpos < len1 || rpos < len2)
	{
	if (lpos == len1)
	{
	merged.push_back(right[rpos++]);
	} else if (rpos == len2)
	{
	merged.push_back(left[lpos++]);
	}
	else if (left[lpos] < right[rpos])
	{
	merged.push_back(left[lpos++]);
	} else {
	merged.push_back(right[rpos++]);
	}
	}
	return merged;
	}
	vector<int> mergelist(vector<int>& list1,vector<int>& list2, vector<int>& list3)
	{
	vector<int> result;
	vector<int> merged;
	merged = merge(list1, list2);
	result = merge(merged, list3);
	return result;
	}
	int main()
	{
	vector<int>input1;
	input1.push_back(3);
	input1.push_back(7);
	input1.push_back(9);
	input1.push_back(15);
	input1.push_back(35);
	vector<int>input2;
	input2.push_back(2);
	input2.push_back(8);
	input2.push_back(45);
	input2.push_back(60);
	input2.push_back(70);
	input2.push_back(100);
	vector<int>input3;
	input3.push_back(5);
	input3.push_back(6);
	input3.push_back(50);
	input3.push_back(101);
	input3.push_back(110);
	vector<int> result = mergelist(input1, input2, input3);
	for(int i = 0; i < result.size(); i++)
	{
	cout<<result[i]<<",";
	}
	cout<<endl;
	return 1;
	}

view raw mergelist.cpp hosted with ❤ by GitHub

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)$

	# code
	class MinHeap:
	def __init__(self):
	self.list =[None]
	def length(self):
	return len(self.list) - 1
	def swap(self, src, dst):
	tmp = self.list[src]
	self.list[src] = self.list[dst]
	self.list[dst] = tmp
	def parent(self, child):
	return child // 2
	def left(self, parent):
	return 2 * parent
	def right(self, parent):
	return 2 * parent + 1
	def extract(self):
	if self.length() == 0:
	return None
	value = self.list[1]
	self.swap(1, len(self.list) - 1)
	self.list.pop()
	self.bubble_down(1)
	return value
	def add(self, value):
	self.list.append(value)
	self.bubble_up(len(self.list) - 1)
	print(self.list)
	def is_child(self, parent, child):
	return self.list[parent][0] < self.list[child][0]
	def bubble_down(self, parent):
	if parent >= self.length():
	return
	left = self.left(parent)
	if left > self.length():
	return
	right = self.right(parent)
	to_swap = left if right > self.length() or self.is_child(left, right) else right
	if self.is_child(parent, to_swap) != True:
	self.swap(parent, to_swap)
	self.bubble_down(to_swap)
	def bubble_up(self, child):
	if child <= 1:
	return
	parent = self.parent(child)
	if parent <= 0:
	return
	if self.is_child(parent, child) !=True:
	self.swap(parent, child)
	self.bubble_up(parent)
	def three_way_merge(arr1, arr2, arr3):
	# curr index for three arrays
	i = 0
	j = 0
	k = 0
	output = []
	heap = MinHeap()
	while (i < len(arr1) or j < len(arr2) or k < len(arr3)): # i = 4, j = 3, k = 2, heap=[], output = [2,3, 5, 6,7,8,9, 15, 45]
	if heap.length() == 0:
	# add new elements from each array
	if i < len(arr1):
	heap.add([arr1[i], 0])
	i = i + 1
	if j < len(arr2):
	heap.add([arr2[j], 1])
	j = j + 1
	if k < len(arr3):
	heap.add([arr3[k], 2])
	k = k + 1
	else:
	# pull the smallest from the heap
	next = heap.extract()
	output.append(next[0])
	if next[1] == 0:
	if i < len(arr1):
	heap.add([arr1[i], 0])
	i = i + 1
	elif next[1] == 1:
	if j < len(arr2):
	heap.add([arr2[j], 1])
	j = j + 1
	elif next[1] == 2:
	if k < len(arr3):
	heap.add([arr3[k], 2])
	k = k + 1
	return output
	# test
	arr1 = [3,7,9,15]
	arr2 = [2,8,45,60,70,100]
	arr3 = [5, 6, 50,101, 110]
	result = three_way_merge(arr1, arr2, arr3)
	print ("result = {}".format(result))

view raw three_way_merge.py hosted with ❤ by GitHub

20:00: to write up the minHeap

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