Sorting Made Simple: Implementing Merge Sort in JavaScript

Here's an implementation of Merge Sort in JavaScript with detailed comments to help explain each step:

javascriptCopy codefunction mergeSort(arr) {
  // Base case: if the array has one or fewer elements, it is already sorted
  if (arr.length <= 1) {
    return arr;
  }

  // Split the array in half
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  // Recursively sort the left and right halves
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);

  // Merge the sorted halves
  return merge(sortedLeft, sortedRight);
}

function merge(left, right) {
  const merged = [];

  // While both arrays have elements, compare the first elements of each and add the smaller one to the merged array
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      merged.push(left.shift());
    } else {
      merged.push(right.shift());
    }
  }

  // Add any remaining elements of the left or right array to the merged array
  return [...merged, ...left, ...right];
}

// Example usage
const unsortedArray = [38, 27, 43, 3, 9, 82, 10];
const sortedArray = mergeSort(unsortedArray);
console.log(sortedArray); // [3, 9, 10, 27, 38, 43, 82]

In this example, the mergeSort function takes an unsorted array and returns a sorted array using the Merge Sort algorithm. The merge function is a helper function that takes two sorted arrays and returns a single sorted array by comparing the first elements of each array and adding the smaller one to a new array until one of the arrays is empty, and then adding the remaining elements of the non-empty array to the new array.

When we call mergeSort on the example unsorted array [38, 27, 43, 3, 9, 82, 10], the algorithm works as follows:

1. The mergeSort function is called with the unsorted array [38, 27, 43, 3, 9, 82, 10].

2. Since the array has more than one element, it is split in half: [38, 27, 43, 3] and [9, 82, 10].

3. The mergeSort function is recursively called on each half, resulting in the sorted arrays [3, 27, 38, 43] and [9, 10, 82].

4. The merge function is called with the two sorted arrays, resulting in the sorted array [3, 9, 10, 27, 38, 43, 82].

5. The mergeSort function returns the sorted array to the caller.

6. The sorted array [3, 9, 10, 27, 38, 43, 82] is logged to the console.