Algorithm to merge two sorted array

Learn how to implement an algorithm to merge two sorted array in javascript.

Example

Merged two array sorted in descending order

Input:
[11, 9, 7, 6, 5]
[15, 12, 10, 8, 6]

Output:
[15, 12, 11, 10, 9, 8, 7, 6, 6, 5]

Merged two array sorted in ascending order

Input:
[5, 6, 7, 9, 11] 
[6, 8, 10, 12, 15]

Output:
[5, 6, 6, 7, 8, 9, 10, 11, 12, 15]

Implementation

• We will use a function which will merge the two array which are sorted in ascending or descending order. To determine the merging order we will pass an extra Boolean argument.
• We are going to use a temporary array for the merging and two variables to keep track of the given two arrays index positions.
• Then we will loop until the all the elements of any one given array has been merged.
• In the loop, based on the merging order like if we are merging for arrays sorted in ascending order then we will check if element of first array is less than element of second array and add the first array’s element else add the second array’s element. If the arrays are sorted in descending order then will do the reverse of it.
• After the end of the loop we will add the remaining elements of both the arrays to merge them.

let mergeArrays = (arr1, arr2, desc = false, l1 = arr1.length, l2 = arr2.length) => {
  
  let merge = [];
  let i = 0, j = 0; //To keep track of the merging order
  
  if(!desc){
    //If the sorted arrays are in descending order 
    //Then merge accordingly
    while(i < l1 && j < l2){
      if(arr1[i] < arr2[j]){
        merge.push(arr1[i++]);
      }else{
        merge.push(arr2[j++]);
      }
    }
  }else{
    //If the sorted arrays are in ascending order 
    //Then merge accordingly
    while(i < l1 && j < l2){
      if(arr1[i] > arr2[j]){
        merge.push(arr1[i++]);
      }else{
        merge.push(arr2[j++]);
      }
    }
  }
  
  //Add the remaining elements of first array.
  while(i < l1){
    merge.push(arr1[i++]);
  }
  
  //Add the remaining elements of second array.
  while(j < l2){
    merge.push(arr2[j++]);
  }
  
  //Return the merged array.
  return merge;
}

Input:
//Merge arrays sorted in descending order
console.log(mergeArrays([11, 9, 7, 6, 5], [15, 12, 10, 8, 6], true));

//Merge arrays sorted in ascending order
console.log(mergeArrays([5, 6, 7, 9, 11], [6, 8, 10, 12, 15]));

Output:
[15, 12, 11, 10, 9, 8, 7, 6, 6, 5]
[5, 6, 6, 7, 8, 9, 10, 11, 12, 15]

Time complexity: O(n1 + n2);
Space complexity: O(n1 + n2);

Time and Space complexity

• We are merging both the given arrays by looping them together until we have merge all elements of both the arrays, so Time complexity is O(n1 + n2), where n1 is the length of first array and n2 is the length of the second array.
• We are using another array to merge the given two arrays, so Space complexity is O(n1 + n2).