Merge a small sorted array into a larger sorted array

© Parineeth M R

Question 44. Given a small array of size n having n sorted elements and a big array of size m+n having m sorted elements at the beginning of the big array, merge the two arrays and store them in the big array


There is just enough free space in the big array to accommodate the elements of the small array. The two sorted arrays can be merged in O(m+n). The trick is to start filling up the big array from the end where the free space is present. The code for this is given below

C/C++


/*
a: array of size m+n which has m elements at beginning and n spaces at end
b: array of size n with n elements
m: number of elements in array a
n: number of elements in array b
*/
void merge_arrays(int a[], int b[], int m, int n)
{
	int i, j, fill_pos;

	i = m - 1;
	j = n - 1;
	fill_pos = m + n - 1; /*Start filling from the rear of the array*/

	while (i >= 0 && j >= 0) {
		if (a[i] > b[j]) {
			a[fill_pos--] = a[i--];
		} else {
			a[fill_pos--] = b[j--];
		}
	}

	/*Fill up the remaining elements of array a if any*/
	while (i >= 0)
		a[fill_pos--] = a[i--];

	/*Fill up the remaining elements of array b if any*/
	while (j >= 0)
		a[fill_pos--] = b[j--];

} 



Java


/*
a: array of size m+n which has m elements at beginning and n spaces at end
b: array of size n with n elements
m: number of elements in array a
n: number of elements in array b
*/
public static void mergeArrays(int[] a, int[] b, int m, int n) 	{
	int i = m - 1;
	int j = n - 1;
	int fillPos = m + n - 1; /*Start filling from the rear of the array*/

	while (i >= 0 && j >= 0) {
		if (a[i] > b[j]) {
			a[fillPos--] = a[i--];
		} else {
			a[fillPos--] = b[j--];
		}
	}

	/*Fill up the remaining elements of array a if any*/
	while (i >= 0)
		a[fillPos--] = a[i--];

	/*Fill up the remaining elements of array b if any*/
	while (j >= 0)
		a[fillPos--] = b[j--];
}  



Python


#a: list of size m+n which has m elements at beginning 
#b: list of size n with n elements
#m: number of elements in list a
#n: number of elements in list b
def merge_lists(a, b, m, n) :
	i = m - 1
	j = n - 1
	fill_pos = m + n - 1 #Start filling from the rear of list a

	while (i >= 0 and j >= 0) :
		if (a[i] > b[j]) :
			a[fill_pos] = a[i]
			fill_pos -= 1
			i -= 1
		else :
			a[fill_pos] = b[j]
			fill_pos -= 1
			j -= 1
		
	#Fill up the remaining elements of list a if any
	while (i >= 0):
		a[fill_pos] = a[i]
		fill_pos -= 1
		i -= 1

	#Fill up the remaining elements of list b if any
	while (j >= 0):
		a[fill_pos] = b[j]
		fill_pos -= 1
		j -= 1