41.implement-Merge-Sort.md

41. implement Merge Sort

Merge Sort is a divide-and-conquer algorithm that splits the input list into smaller sublists, sorts those sublists, and then merges them back together to produce a sorted list.

Problem

https://bigfrontend.dev/problem/implement-Merge-Sort

Problem Description

Even for Front-End Engineer, it is a must to understand how basic sorting algorithms work.

Now you are asked to implement Merge Sort, which sorts an integer array in ascending order.

Do it in-place, no need to return anything.

Follow-up

What is time cost for average / worst case ? Is it stable?

Solution

/**
 * @param {number[]} arr
 */
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const middle = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, middle));
  const right = mergeSort(arr.slice(middle));
  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// Usage 
console.log(mergeSort([1, 5, 3, 8, 2, 6, 4, 7])); // [1, 2, 3, 4, 5, 6, 7, 8]
console.log(mergeSort([1, 5, 3, 8, 2, 6, 4])); // [1, 2, 3, 4, 5, 6, 8]
console.log(mergeSort([1, 5, 3, 8, 2, 6])); // [1, 2, 3, 5, 6, 8]
console.log(mergeSort([1, 5, 3, 8, 2])); // [1, 2, 3, 5, 8]
console.log(mergeSort([1, 5, 3, 8])); // [1, 3, 5, 8]
console.log(mergeSort([1, 5, 3])); // [1, 3, 5]
console.log(mergeSort([1, 5])); // [1, 5]
console.log(mergeSort([1])); // [1]
console.log(mergeSort([])); // []

Use Cases:

1. Large Data Sets: Efficient for large datasets due to its O(nlog⁡n)O(n \log n)O(nlogn) complexity.
2. Linked Lists: Works well with linked lists where random access is not required.
3. External Sorting: Useful for sorting large amounts of data that do not fit into memory.