Question

How to implement the merge sort algorithm in JavaScript

Answer 1

/**
 * merge(left, right)
 * -------------------
 * Merges two **sorted** arrays into one sorted array.
 * This version uses shift(), which removes the first element of an array.
 */
function merge(left, right) {
    let arr = []; // final merged result
   
    // Continue while both arrays still have elements
    while (left.length && right.length) {
        // Compare the first elements of each array
        if (left[0] < right[0]) {
            arr.push(left.shift()); // take from left
        } else {
            arr.push(right.shift()); // take from right
        }
    }
   
    // One of the arrays may still have leftover elements.
    // Spread syntax appends whatever remains.
    return [...arr, ...left, ...right];
}

/**
 * mergeSort(arr)
 * ----------------
 * Recursively splits the array into halves, sorts each half,
 * and merges them back together.
 *
 * NOTE: This version mutates the array using splice().
 */
function mergeSort(arr, halflength = arr.length / 2) {
    // Base case: arrays with fewer than 2 elements are already sorted
    if (arr.length < 2) {
        return arr;
    }
   
    // Remove the first half of the array and store it in "left"
    const left = arr.splice(0, halflength);
   
    // Recursively sort the left half and the remaining right half
    return merge(mergeSort(left), mergeSort(arr));
}

let arr = [10, 8, 5, 4, 3, 6, 2, 7, 1, 9];

console.log(mergeSort(arr));

/*
Explanation:
------------
This implementation of merge sort works in three phases:

1. DIVIDE:
   mergeSort() splits the array into two halves using splice().
   It keeps splitting until each subarray has only one element.

2. CONQUER:
   Each half is sorted recursively.

3. COMBINE:
   The merge() function compares the first elements of each sorted half
   and builds a new sorted array by repeatedly taking the smaller value.



run:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

*/

 

70+ SQL courses for beginners and professionals

Answer 2

/**
 * merge(left, right)
 * -------------------
 * Takes two **sorted** arrays and merges them into a single sorted array.
 * This function does NOT mutate the input arrays.
 */
function merge(left, right) {
  const result = [];
  let i = 0; // pointer for left array
  let j = 0; // pointer for right array

  // Compare elements from both arrays and push the smaller one
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]); // take from left, then move pointer
    } else {
      result.push(right[j++]); // take from right, then move pointer
    }
  }

  // If one array still has remaining elements, append them
  // Only one of these slices will contain elements
  return result
    .concat(left.slice(i))
    .concat(right.slice(j));
}

/**
 * mergeSort(arr)
 * ----------------
 * Recursively splits the array into halves, sorts each half,
 * and merges them back together.
 */
function mergeSort(arr) {
  // Base case: arrays with 0 or 1 element are already sorted
  if (arr.length <= 1) return arr;

  // Find the midpoint of the array
  const mid = Math.floor(arr.length / 2);

  // Recursively sort the left and right halves
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  // Merge the two sorted halves
  return merge(left, right);
}


const arr = [88, 17, 36, 4, 9, 91, 15];

console.log(mergeSort(arr));


/*
Explanation:
------------
Merge sort works in three main steps:

1. DIVIDE:
   The array is repeatedly split into two halves until each subarray
   contains only one element. A single-element array is already sorted.

2. CONQUER:
   Each half is sorted recursively using mergeSort().

3. COMBINE:
   The merge() function takes two sorted arrays and merges them into
   one sorted array by comparing elements one by one.



run:

[ 4, 9, 15, 17, 36, 88, 91 ]

*/

 

70+ SQL courses for beginners and professionals