Merge two sorted array A and B, where A has larger buffer to hold B at the end of it.

Problem

You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write the algorithm to merge A and B without allocation additional memory.

Answer

Merging integers backward,  $O(N)$

Given the fact that array A has free space at the end to hold array B. (See Figure 1.)

It is similar to the merge step of the Merge sort except for the fact that we are merging the array B into A.

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

Here is the complete code in C++.

	#include<iostream>
	using namespace std;
	void merge(int* larger, int llen, int llast, int * smaller, int slen)
	{
	int spos = slen-1;
	int lpos = llast;
	int cur = llen-1;
	while(spos >=0 || lpos >=0)
	{
	if (lpos < 0)
	{
	larger[cur--] = smaller[spos--];
	} else if (spos < 0)
	{
	larger[cur--] = larger[lpos--];
	}
	else if (larger[lpos] > smaller[spos])
	{
	larger[cur--] = larger[lpos--];
	} else {
	larger[cur--] = smaller[spos--];
	}
	}
	}
	int main()
	{
	int larger[10] = {1,5,8,10,14,17,0,0,0,0};
	int smaller[4] = {2,4,6,13};
	merge(larger, 10, 5, smaller, 4);
	for(int i = 0; i < 10; i++)
	cout<<larger[i]<<",";
	cout<<endl;
	return 1;
	}

view raw merge_array_into_larger_one.cpp hosted with ❤ by GitHub

Python solution

	'''
	You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write the algorithm to merge A and B without allocation additional memory.
	'''
	def find_last_pos(input):
	for i, v in enumerate(input):
	if (v is None):
	return i - 1
	return i
	def merge_list(shorter, longer):
	if len(longer) - len(shorter) < len(shorter):
	return None
	curpos = len(longer) - 1
	lpos = find_last_pos(longer)
	spos = len(shorter) -1
	while lpos >= 0 or spos >= 0:
	if spos < 0:
	longer[curpos] = longer[lpos]
	lpos -= 1
	elif lpos < 0:
	longer[curpos] = shorter[spos]
	spos -= 1
	elif shorter[spos] >= longer[lpos]:
	longer[curpos] = shorter[spos]
	spos-=1
	else:
	longer[curpos] = longer[lpos]
	lpos-=1
	curpos -=1
	return longer
	shorter = [1,5,9,20,100]
	longer = [6,7,20,30,50,None,None,None,None,None]
	merged = merge_list(shorter, longer)
	print merged

view raw merge_short_into_long.py hosted with ❤ by GitHub

Practice statistics

13:51: to write up the code

02:43: to verify the code.

03:00: to check for the typos

UPDATE(2022-06-13): Solved the problem again, the algorithm was sound but had a minor bug.

 Original answers put the merged values from the end of the larger buffer and can leave the duplicate values in front of the larger buffer if the empty space of the buffer is larger than the smaller buffer.  This solution correctly put the merged values in the right position such that the merged values start from zero of the larger buffer.

	'''
	Merge two sorted array A and B, where A has larger buffer to hold B at the end of it
	'''
	def merge_in_place(arr1, arr1_data_len, arr2):
	larger = arr1 if len(arr1) > len(arr2) else arr2
	smaller = arr1 if len(larger) != len(arr1) else arr2
	if len(larger) - arr1_data_len < len(smaller):
	# larger buffer does not have enought space for smaller array
	return None
	current = arr1_data_len + len(smaller) - 1
	lpos = arr1_data_len - 1
	spos = len(smaller) - 1
	while(lpos >= 0 or spos >= 0):
	if spos < 0:
	larger[current] = larger[lpos]
	current = current - 1
	lpos = lpos -1
	elif lpos < 0:
	larger[current] = smaller[spos]
	current = current - 1
	spos = spos -1
	elif larger[lpos] <= smaller[spos]:
	larger[current] = smaller[spos]
	current = current - 1
	spos = spos -1
	else:
	larger[current] = larger[lpos]
	current = current - 1
	lpos = lpos -1
	return larger
	larger = [1,2,5,6, None, None, None]
	smaller = [4, 7, 8]
	merged = merge_in_place(larger, 4, smaller)
	print ("merged = {}".format(merged))
	larger = [1,2,5,6, 10, None, None, None, None, None]
	smaller = [4, 7, 8]
	merged = merge_in_place(larger, 5, smaller)
	print ("merged = {}".format(merged))

view raw merge_in_place.py hosted with ❤ by GitHub