Back To Tutorials

Merge Two Sorted Arrays in JavaScript

Intermediatechallenge

In this challenge, you will implement a function to merge two sorted arrays into one sorted array. This is a common algorithm used in sorting algorithms like Merge Sort. The input arrays are both already sorted, so your task is to combine them in such a way that the resulting array remains sorted.

This challenge emphasizes handling edge cases like empty arrays and optimizing the solution to have O(n + m) time complexity, where n and m are the lengths of the two arrays.

Objective:

  • Implement a function that takes two sorted arrays as input and returns a new array containing all the elements from both input arrays in sorted order.

Requirements:

  1. Write a function mergeSortedArrays(arr1, arr2) that:
    • Accepts two sorted arrays as input.
    • Returns a single sorted array that merges the two arrays.
    • Handle cases where one or both arrays may be empty.
  2. The function should have a time complexity of O(n + m) where n and m are the lengths of the input arrays.

Steps:

  1. Setup:

    • Create two sorted arrays, arr1 and arr2, that contain integers.
    • Define the function mergeSortedArrays(arr1, arr2).

  2. Merge Logic:

    • Initialize two pointers (i and j) to track the current position in arr1 and arr2.
    • Use a loop to iterate through both arrays:
      • Compare the current elements of arr1 and arr2 and push the smaller element into the result array.
      • Move the pointer forward in the array from which the element was taken.
    • Once you finish one array, add the remaining elements of the other array to the result.

  3. Test the Function:

    • Test with two non-empty sorted arrays to ensure the result is merged correctly.
    • Test with edge cases such as one or both arrays being empty.
    • Test with arrays that contain duplicates or are of unequal length.

Resources:

Solution:

Here is a solution for merging two sorted arrays:

// Function to merge two sorted arrays
function mergeSortedArrays(arr1, arr2) {
  let mergedArray = [];
  let i = 0, j = 0;

  // Loop until one of the arrays is fully traversed
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      mergedArray.push(arr1[i]);
      i++;
    } else {
      mergedArray.push(arr2[j]);
      j++;
    }
  }

  // Add remaining elements of arr1 (if any)
  while (i < arr1.length) {
    mergedArray.push(arr1[i]);
    i++;
  }

  // Add remaining elements of arr2 (if any)
  while (j < arr2.length) {
    mergedArray.push(arr2[j]);
    j++;
  }

  return mergedArray;
}

// Example Usage
const arr1 = [1, 3, 5, 7];
const arr2 = [2, 4, 6, 8, 10];

const result = mergeSortedArrays(arr1, arr2);
console.log(result); // Output: [1, 2, 3, 4, 5, 6, 7, 8, 10]