Merge Sort in JavaScript (O(n log n) Time Complexity)

In this video lesson we will study how the Merge Sort algorithm works, we will analyze its time and space complexities and then we will implement it:

Problem - Merge Sort:

Given an array of integers nums, sort it in ascending order using Merge Sort

Example 1:

Input: nums = [3, 1, 3, 2, 5, 4]
Output: [1, 2, 3, 3, 4, 5]

Note:

Your algorithm should run in O(n log n) time and use O(n) extra space.

Understanding the Problem

The core challenge of the problem is to sort an array of integers efficiently. Merge Sort is a classic algorithm that divides the array into smaller subarrays, sorts them, and then merges them back together. This divide-and-conquer approach ensures that the sorting is done in O(n log n) time complexity, which is optimal for comparison-based sorting algorithms.

Merge Sort is significant in various applications, including external sorting (sorting data that doesn't fit into memory) and parallel processing. However, it requires O(n) extra space, which can be a limitation in memory-constrained environments.

Approach

To solve the problem, we can break it down into the following steps:

Divide the array into two halves.
Recursively sort each half.
Merge the two sorted halves back together.

Let's start with a naive approach:

Naive Approach: We could use a simple sorting algorithm like Bubble Sort or Insertion Sort, but these have O(n^2) time complexity, which is not efficient for large arrays.

Optimized Approach: Merge Sort is an optimized approach with O(n log n) time complexity. It works by recursively dividing the array into smaller subarrays, sorting them, and then merging them back together.

Algorithm

Here is a step-by-step breakdown of the Merge Sort algorithm:

Divide: Split the array into two halves.
Conquer: Recursively sort each half.
Combine: Merge the two sorted halves back together.

Code Implementation

/**
 * Merge Sort function
 * @param {number[]} nums - The array of integers to be sorted
 * @return {number[]} - The sorted array
 */
function mergeSort(nums) {
  // Base case: if the array has 1 or 0 elements, it is already sorted
  if (nums.length <= 1) {
    return nums;
  }

  // Divide the array into two halves
  const mid = Math.floor(nums.length / 2);
  const left = nums.slice(0, mid);
  const right = nums.slice(mid);

  // Recursively sort each half
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);

  // Merge the sorted halves
  return merge(sortedLeft, sortedRight);
}

/**
 * Merge function to combine two sorted arrays
 * @param {number[]} left - The sorted left half
 * @param {number[]} right - The sorted right half
 * @return {number[]} - The merged and sorted array
 */
function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

  // Merge the two arrays by comparing elements
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  // Add any remaining elements from the left array
  while (i < left.length) {
    result.push(left[i]);
    i++;
  }

  // Add any remaining elements from the right array
  while (j < right.length) {
    result.push(right[j]);
    j++;
  }

  return result;
}

// Example usage
const nums = [3, 1, 3, 2, 5, 4];
console.log(mergeSort(nums)); // Output: [1, 2, 3, 3, 4, 5]

Complexity Analysis

The time complexity of Merge Sort is O(n log n) because the array is divided into halves log n times, and the merging process takes linear time. The space complexity is O(n) due to the additional arrays used for merging.

Edge Cases

Potential edge cases include:

An empty array: The output should be an empty array.
An array with one element: The output should be the same array.
An array with duplicate elements: The algorithm should handle duplicates correctly.

Examples:

mergeSort([]); // Output: []
mergeSort([1]); // Output: [1]
mergeSort([2, 1, 2]); // Output: [1, 2, 2]

Testing

To test the solution comprehensively, consider using a variety of test cases:

Simple cases: Small arrays with a few elements.
Complex cases: Large arrays with many elements.
Edge cases: Empty arrays, arrays with one element, arrays with duplicate elements.

Testing frameworks like Jest or Mocha can be used to automate the testing process.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller, manageable parts.
Think about the base case and the recursive case.
Consider the time and space complexity of your solution.
Practice solving similar problems to improve your problem-solving skills.

Conclusion

Merge Sort is a powerful sorting algorithm with O(n log n) time complexity. Understanding and implementing it helps in solving various sorting problems efficiently. Practice and explore further to master this algorithm.

Additional Resources

For further reading and practice problems, consider the following resources: