General

No Comments

Implementing Merge Sort in JavaScript

Merge Sort is a classic sorting algorithm that uses the divide and conquer paradigm to efficiently sort an array, this is one of the most asked interview questions.

Steps of Merge Sort

  1. Divide: Split the array into two halves.
  2. Conquer: Recursively sort each half.
  3. Combine: Merge the two sorted halves into a single sorted array.

Detailed Implementation in JavaScript

Let’s implement Merge Sort step-by-step in JavaScript.

Step 1: Splitting the Array

First, we need a function to split the array into two halves.

function mergeSort(arr) {
  // Base case: If the array has only one element or is empty
  if (arr.length <= 1) {
    return arr;
  }

  // Find the middle index
  const mid = Math.floor(arr.length / 2);

  // Split the array into left and right halves
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  // Recursively sort the left and right halves
  return merge(mergeSort(left), mergeSort(right));
}

Step 2: Merging Two Sorted Arrays

Next, we need a function to merge two sorted arrays into one sorted array.

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // Compare elements from left and right arrays and add the smaller one to the result
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Concatenate any remaining elements from the left and right arrays
  return result.concat(left.slice(leftIndex))
  .concat(right.slice(rightIndex));
}

Full Implementation

Combining the splitting and merging functions, we get the complete implementation of Merge Sort.

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex))
  .concat(right.slice(rightIndex));
}

// Test the mergeSort function
const array = [34, 7, 23, 32, 5, 62];
const sortedArray = mergeSort(array);
console.log(sortedArray); // Output: [5, 7, 23, 32, 34, 62]

Analyzing Merge Sort

Time Complexity

Merge Sort has a time complexity of O(n log n) in all cases. This is because the array is repeatedly split in half (log n splits) and each split array is processed with a linear time merge operation (n comparisons).

Space Complexity

The space complexity of Merge Sort is O(n) due to the additional space required for the temporary arrays during the merge process. Each recursive call creates new arrays to hold the split halves, leading to additional memory usage.

Close Menu