Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

merge
merge sort
sorting
array

How to merge two sorted arrays into one sorted array

Hafiza Farwa Mahmood

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Sorted arrays

Sorted arrays have sequential arrangements of elements. However, we encounter a problem when we need to merge two sorted arrays into a new sorted array. The idea is to use a merge sorting technique while combining these two sorted arrays.

Click here to learn more about merge sort.

Understanding the problem

Merge sort is used to merge two sorted arrays. Firstly, the merge function compares the elements of both given sorted arrays and adds a smaller element to the new array. After this, it increments the pointer and compares again. We can see this in the example below:

Example

1 of 14

Code

Here's the code for the implementation of merging two sorted arrays:

#Program to merge two sorted arrays in one array
def arrayMerger(array1,array2):
array3= [] #Array3 will contain merged sorted elements of both array1 and array2
i=0 #Counter variables
j=0
k=0
size1 = len(array1)
size2 = len(array2)
while i < size1 and j < size2:
#Comparing the elements of both arrays and storing in new array
if array1[i] < array2[j]:
array3.append(array1[i])
i += 1
else:
array3.append(array2[j])
j += 1
#Store remaining elements of first array
while i < size1:
array3.append(array1[i])
i += 1
#Store remaining elements of second array
while j < size2:
array3.append(array2[j])
j += 1
print 'Array 1:',array1
print 'Array 2:' ,array2
print 'After Merge'
print 'Array 3:',array3
# Driver code
array1 = [2,5,8]
array2 = [1,3,4]
arrayMerger(array1, array2)

Explanation

The merge function of merge sort is used to implement this code. The steps needed to obtain the sorted merge array through this method can be found below:

Line 3–9: We define the arrayMerger function in which we create an array3 that has the size of both given arrays. For example, if the size of array1 is 4, and of array2 is 4. Then the size of array3 is 4+4 =8

Line 11–19: We use the while loop to compare the elements of both array1 and array2 traversing simultaneously and adding the smaller element into array3.

Line 23–31: If some elements are left, copy them into array3.

With that, two sorted arrays have been merged into one array.

Time complexity

The time complexity of this approach is O(m+n)O(m+n), where mm is the number of elements in array1 and nn is the number of elements in array2.

RELATED TAGS

merge
merge sort
sorting
array

CONTRIBUTOR

Hafiza Farwa Mahmood
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring