Learn basic concept of c , c++ and python programming in regularcodes.com

Spread the post

Merge two sorted array

Write efficient program to merge two sorted array.

Example

Consider following test cases of More two sorted array.

1) Given two array are sorted form. In this two array size are equals or there are possible to size are not equal. Example

2) Duplicate array elements are possible in Given array. (merge two sorted arrays with duplicates elements)

Example

Here given all possible solutions

1) merge two sorted arrays using a temporary array.
2) merge two sorted arrays without using third array.
3) merge two sorted arrays using a dynamic array.

1) merge two sorted arrays using a temporary array

Suppose array contain following elements. Befor Merge.

Stack Areamainarray1 [0] 1 [1] 4 [2] 7 [3] 8 [4] 11array2 [0] 3 [1] 13 [2] 19size1 (int) =5size2 (int) =3

After Merge

Stack Areamainarray1 [0] 1 [1] 3 [2] 4 [3] 7 [4] 8array2 [0] 11 [1] 13 [2] 19size1 (int) =5size2 (int) =3

Program for merge two sorted arrays using third array. time complexity O(n).

Output

2) merge two sorted arrays without using a temporary array.

Beforemainarray1 [0] 12 [1] 13 [2] 19array2 [0] 11 [1] 13 [2] 17 [3] 18 [4] 21size1 (int) =3size2 (int) =5 Aftermainarray1 [0] 11 [1] 12 [2] 13array2 [0] 13 [1] 17 [2] 18 [3] 19 [4] 21size1 (int) =3size2 (int) =5

View code animation

Program for merge two sorted arrays with o(1) extra space. Time complexity O(n*m).(m,n size of array).

Output

3) merge two sorted arrays using a dynamic array.

Array elements.

Stack Areamainarray1 [0] 1 [1] 4 [2] 7 [3] 8 [4] 21array2 [0] 3 [1] 13 [2] 19size1 (int) =5size2 (int) =3

View process

Stack Areamainarray1 [0] 1 [1] 3 [2] 4 [3] 7 [4] 8array2 [0] 13 [1] 19 [2] 21size1 (int) =5size2 (int) =3sortarray1(pointer)array2(pointer)i (int) =5index (int) =7j (int) =2size1 (int) =5size2 (int) =3temp(pointer) Heap Areaarray (int) [0] 1 [1] 3 [2] 4 [3] 7 [4] 8 [5] 13 [6] 19 [7] 21

Output

Submit your solution in comment section.

Spread the post

Recommended Posts: