Coding Challenge Practice - Question 95

The task is to implement the merge sort.

The boilerplate code

function mergeSort(arr) {
  // your code here
}

If the array is empty or has 1 element, it is already sorted

if (arr.length <= 1) return arr;

Create a helper function that returns a new sorted array. The function recursively splits the array in half.

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

  const mid = Math.floor(arr.length / 2);

Sort each half independently, and merge the sorted halves

  const left = mergeSortHelper(arr.slice(0, mid));
  const right = mergeSortHelper(arr.slice(mid));

  return merge(left, right);

Copy the sorted array back into the original array

const sorted = mergeSortHelper(arr);
  for (let i = 0; i < arr.length; i++) {
    arr[i] = sorted[i];
  }

Return the original array

return arr;

Given two already sorted arrays, merge both arrays by repeatedly pushing the smaller element to the front

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

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
}

Append any remaining values

return result
    .concat(left.slice(i))
    .concat(right.slice(j));

The final code

function mergeSort(arr) {
  // your code here
  if(arr.length <= 1) return arr;

  const sorted = mergeSortHelper(arr);

  for(let i = 0; i < arr.length; i++) {
    arr[i] = sorted[i];
  }
  return arr;
}

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

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

  return merge(left, right);
}

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

  while(i < left.length && j < right.length) {
    if(left[i] <= right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  return result
  .concat(left.slice(i))
  .concat(right.slice(j));
}

That's all folks!