Mergesort algorithm

Merge sort is an efficient, comparison-based sorting algorithm. It is based on the Divide and Conquer paradigm.

Mergesort performance metrics:

Mergesort complexity analysis

Merge Sort is a popular sorting algorithm that follows the divide-and-conquer approach. It recursively divides the input array into smaller subarrays, sorts them independently, and then merges them to obtain the final sorted array. The complexity of Merge Sort can be analyzed as follows:

Time Complexity:

Best case: O(n log n)
Average case: O(n log n)
Worst case: O(n log n)

Merge Sort has a consistent time complexity of O(n log n) in all cases. This is because it divides the input array into two halves at each level of recursion, and the merge step takes linear time to combine the sorted subarrays. The merging process is performed for each level of recursion, which results in a logarithmic number of levels, giving us a time complexity of O(n log n).

Space Complexity:

Merge Sort has a space complexity of O(n) because it requires additional space to store the subarrays during the sorting process. This is because at each level of recursion, two new subarrays are created. However, the space complexity is still considered efficient because the additional space is deallocated after merging.
In terms of auxiliary space, Merge Sort is an in-place algorithm, meaning it doesn’t require additional space proportional to the input size. It only uses a temporary array during the merging process.

Stability:

Merge Sort is a stable sorting algorithm, meaning it maintains the relative order of elements with equal values. This is achieved during the merge step when comparing and merging elements from the two subarrays.
Merge Sort is widely used and preferred for its consistent time complexity and stability, making it suitable for various applications where a stable, efficient sorting algorithm is required.

Mergesort code example

const merge = (left, right) => {
  const sortedArr = []
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      sortedArr.push(left.shift())
    } else {
      sortedArr.push(right.shift())
    }
  }

  return [...sortedArr, ...left, ...right]
}   

const mergeSort = (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)
};

const unsortedList = [23, 45, 16, 37, 3, 99, 22];
const sortedList = mergeSort(unsortedList);

console.log(sortedList); // [3, 16, 22, 23, 37, 45, 99]