Definition

Merge sort is an efficient, general-purpose, comparison-based sorting algorithm.

Merge sort is divide and conquer algorithm, based on the idea of breaking down a array into several subarrays until each one consists of a single element and merging those subarrays in a manner that results into a sorted array.

Implementation

• Use recursion.

• If the length of the array is less than 2, return the array.

• Use Math.floor() to calculate the middle point of the array.

• Use Array.prototype.slice() to slice the array in two and recursively call megerSort() on the created subarrays.

• Finally, use Array.from() and Array.prototype.shift() to combine the two sorted subarrays into one.

const mergeSort = (arr) => {
  if (arr.length < 2) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = megerSort(arr.slice(0,mid));
  const right = megerSort(arr.slice(mid, arr.length));
  return Array.from({length: left.length + right.length}, () => {
    if (!left.length) return right.shift();
    else if (!right.length) return left.shift();
    else return left[0] > right[0] ? right.shift() : left.shift();
  });
};

mergeSort([5,1,4,2,3]); // [1,2,3,4,5]

Complexity

The algorithm has an average time complexity of O(n log n), where n is the size of the input array.