Merge Sort Algorithm in javascript

mergesort.js

/**
 * ************************************************ MERGE SORT *****************************************************
 *
 *                            [38, 27, 43, 3, 9, 82, 10, 900, 78, 80, 11]
 *                                  /                               \
 *                   [38, 27, 43, 3, 9, 82]                   [10, 900, 78, 80, 11]
 *                       /            \                           /              \
 *               [38, 27, 43]        [3, 9, 82]            [10, 900, 78]        [ 80, 11 ]
 *                  /    \             /     \                 /     \            /     \
 *             [38, 27] [ 43 ]      [3, 9]  [ 82 ]       [10, 900]  [ 78 ]      [ 80 ] [ 11 ]
 *              /    \      \        /   \     \          /     \       \          \    /
 *          [ 38 ] [ 27 ]  [43 ]  [ 3 ] [ 9]  [82 ]     [ 10 ]  [ 900] [78 ]    [ 11, 80 ] // first sorted merge
 *              \     /      \       \   /      \         \     /        \          |
 *             [ 27, 38 ]   [43 ]   [ 3, 9 ]   [82 ]     [10, 900]      [78 ]   [ 11, 80]
 *                   \      /          \      /                 \      /            |
 *               [27, 38, 43]        [3, 9, 82]            [10, 78, 900]        [11, 80]
 *                       \              /                         \              /
 *                   [3, 9, 27, 38, 43, 82]                   [10, 11, 78, 80, 900]
 *                                  \                                /
 *                             [3, 9, 10, 11, 27, 38, 43, 78, 80, 82, 900]
 *
 * ************************************************ MERGE SORT *****************************************************
 */

// ----------------------------------------- Merge Sort Algorithm ------------------------------------------

/**
 * mergeSort - Sort the array using merge sort method
 * @param {Array} arr
 */
const mergeSort = arr => {
  // return the array if length is 1
  if (arr.length == 1) {
    return arr;
  }

  // ceil the half, for odd left side will always 1+
  let half = Math.ceil(arr.length / 2);

  // slice the array
  let leftSide = arr.slice(0, half);
  let rightSide = arr.slice(half, arr.length);

  // if length is greater than 1
  // divide it again
  if (leftSide.length > 1) {
    leftSide = mergeSort(leftSide);
  }

  if (rightSide.length > 1) {
    rightSide = mergeSort(rightSide);
  }

  // return the sorted merge result
  return compareAndMerge(leftSide, rightSide);
};

/**
 * compareAndMerge - Compare the left and the right side and
 * return the merged sorted array
 * @param {Array} leftSide - left side of the array
 * @param {Array} rightSide - right side of the array
 */
const compareAndMerge = (leftSide, rightSide) => {
  // create an empty array
  // this will be the sorted merged array of 2 sides
  let sorted = [];

  // create 2 indexes
  // i for leftSide
  // j for rightSide
  let i = 0;
  let j = 0;

  // compare rightSide with leftSide
  // leftSide is the reference
  while (i < leftSide.length) {
    // compare leftSide at index i to the rightSide at index j
    while (j < rightSide.length) {
      // if leftSide is lesser than rightSide than push the leftSide[i] to sorted array
      if (leftSide[i] < rightSide[j]) {
        sorted.push(leftSide[i]);

        // increment the leftSide index
        // as value at this is pushed into the sorted array
        i++;
      } else {
        // check if all the values at leftSide is pushed into the sorted Array
        // or if all the values at leftSide is sorted
        if (i >= leftSide.length) {
          // Since all the values of leftSide is sorted
          // it will throw an error while checking as index out of range for leftSide[i]
          // All the rest of the values in the rightSide is already sorted
          // Slice the remaining rightSide values
          // concat or add them to the sorted array
          sorted = sorted.concat(rightSide.slice(j, rightSide.length));

          // break the loop
          break;
        }

        // if rightSide is lesser than leftSide at index j and i resp
        // push the rightSide value to the sorted array
        sorted.push(rightSide[j]);

        // increment the rightSide index
        // as value at this is pushed into the sorted array
        j++;
      }
    }

    // check if all the values at rightSide is pushed into the sorted Array
    // or if all the values at rightSide is sorted
    if (j >= rightSide.length) {
      // Since all the values of rightSide is sorted
      // it will throw an error while checking as index out of range for rightSide[j]
      // All the rest of the values in the leftSide is already sorted
      // Slice the remaining leftSide values
      // concat or add them to the sorted array
      sorted = sorted.concat(leftSide.slice(i, leftSide.length));

      // All the values are sorted
      // break the loop
      break;
    }
  }

  //   console.log(sorted);

  // return the sorted merged array
  return sorted;
};

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10, 900, 78, 80, 11]));


/**
 * OUTPUT
 * 
 * [ 38, 27, 43, 3, 9, 82 ] [ 10, 900, 78, 80, 11 ]
 * [ 38, 27, 43 ] [ 3, 9, 82 ]
 * [ 38, 27 ] [ 43 ]
 * [ 38 ] [ 27 ]
 * [ 38 ] [ 27 ]
 * [ 27, 38 ]
 * [ 27, 38 ] [ 43 ]
 * [ 27, 38, 43 ]
 * [ 3, 9 ] [ 82 ]
 * [ 3 ] [ 9 ]
 * [ 3 ] [ 9 ]
 * [ 3, 9 ]
 * [ 3, 9 ] [ 82 ]
 * [ 3, 9, 82 ]
 * [ 27, 38, 43 ] [ 3, 9, 82 ]
 * [ 3, 9, 27, 38, 43, 82 ]
 * [ 10, 900, 78 ] [ 80, 11 ]
 * [ 10, 900 ] [ 78 ]
 * [ 10 ] [ 900 ]
 * [ 10 ] [ 900 ]
 * [ 10, 900 ]
 * [ 10, 900 ] [ 78 ]
 * [ 10, 78, 900 ]
 * [ 80 ] [ 11 ]
 * [ 80 ] [ 11 ]
 * [ 11, 80 ]
 * [ 10, 78, 900 ] [ 11, 80 ]
 * [ 10, 11, 78, 80, 900 ]
 * [ 3, 9, 27, 38, 43, 82 ] [ 10, 11, 78, 80, 900 ]
 * [ 3, 9, 10, 11, 27, 38, 43, 78, 80, 82, 900 ]
 */