Merge Two Sorted Arrays

Merging two sorted arrays into a single sorted array is a classic computer science problem with applications in various fields, from database management to data analysis. This post will look at efficient ways to accomplish this task in JavaScript, providing clear explanations and code examples.

Understanding the Problem

The challenge is straightforward: given two sorted arrays, arr1 and arr2, create a new array mergedArr that contains all elements from both input arrays, also sorted in ascending order. We’ll aim for solutions that are both efficient in terms of time complexity and easy to understand.

Method 1: Using the concat() and sort() Methods

This is the simplest approach, though not necessarily the most efficient for very large arrays. We first concatenate the two arrays using concat(), and then sort the resulting array using the built-in sort() method.

function mergeSortedArraysConcatSort(arr1, arr2) {
  const mergedArr = arr1.concat(arr2);
  mergedArr.sort((a, b) => a - b); // Important: Use a comparison function for numerical sorting
  return mergedArr;
}

// Example usage:
const arr1 = [2, 5, 8, 12];
const arr2 = [1, 3, 6, 9, 11];
const merged = mergeSortedArraysConcatSort(arr1, arr2);
console.log(merged); // Output: [1, 2, 3, 5, 6, 8, 9, 11, 12]

Time Complexity: O(m log(m+n)), where ‘m’ and ‘n’ are the lengths of arr1 and arr2 respectively. The concat operation is O(m+n), and the sort operation is O((m+n) log(m+n)).

Space Complexity: O(m+n) due to the creation of the new mergedArr.

Method 2: Merge Sort Approach (More Efficient)

For better performance with larger arrays, a merge sort-like approach offers a more efficient solution with a time complexity of O(m+n). This method iterates through both arrays simultaneously, comparing elements and adding the smaller element to the result array.

function mergeSortedArraysEfficient(arr1, arr2) {
  let mergedArr = [];
  let i = 0;
  let j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      mergedArr.push(arr1[i]);
      i++;
    } else {
      mergedArr.push(arr2[j]);
      j++;
    }
  }

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

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

  return mergedArr;
}

// Example usage:
const arr3 = [2, 5, 8, 12];
const arr4 = [1, 3, 6, 9, 11];
const mergedEfficient = mergeSortedArraysEfficient(arr3, arr4);
console.log(mergedEfficient); // Output: [1, 2, 3, 5, 6, 8, 9, 11, 12]

Time Complexity: O(m+n) – This is more efficient than the previous method for large arrays.

Space Complexity: O(m+n) – A new array is still created to store the merged result.

Choosing the Right Method

The concat() and sort() method is simpler to write but less efficient for large datasets. The merge sort approach is more complex but provides a significant performance improvement for larger arrays. Choose the method that best suits your needs based on the size of your input arrays and the performance requirements of your application. For most practical purposes, especially with larger datasets, the efficient merge sort approach is recommended.