How to merge two sorted arrays into one sorted array

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

#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)$ , where $m$ is the number of elements in array1 and $n$ is the number of elements in array2.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

YouTubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.