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.

### 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:

1 of 14

### Code

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

#Program to merge two sorted arrays in one arraydef 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 codearray1 = [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)$, where $m$ is the number of elements in array1 and $n$ is the number of elements in array2.

RELATED TAGS

merge
merge sort
sorting
array

CONTRIBUTOR Hafiza Farwa Mahmood 