1/**
2 * Merge Sort implementation for JavaScript arrays
3 * @param {Array} arr - The array to sort
4 * @returns {Array} - A new sorted array
5 */
6function mergeSort(arr) {
7  // Base case: arrays with 0 or 1 element are already sorted
8  if (arr.length <= 1) return arr;
9  
10  // Split array into two halves
11  const mid = Math.floor(arr.length / 2);
12  const left = arr.slice(0, mid);
13  const right = arr.slice(mid);
14  
15  // Recursively sort both halves
16  const sortedLeft = mergeSort(left);
17  const sortedRight = mergeSort(right);
18  
19  // Merge the sorted halves
20  return merge(sortedLeft, sortedRight);
21}
22
23/**
24 * Merge two sorted arrays into one sorted array
25 * @param {Array} left - First sorted array
26 * @param {Array} right - Second sorted array
27 * @returns {Array} - Merged sorted array
28 */
29function merge(left, right) {
30  let result = [];
31  let leftIndex = 0;
32  let rightIndex = 0;
33  
34  // Compare elements from both arrays and add the smaller one to the result
35  while (leftIndex < left.length && rightIndex < right.length) {
36    if (left[leftIndex] < right[rightIndex]) {
37      result.push(left[leftIndex]);
38      leftIndex++;
39    } else {
40      result.push(right[rightIndex]);
41      rightIndex++;
42    }
43  }
44  
45  // Add any remaining elements from both arrays
46  return result.concat(left.slice(leftIndex), right.slice(rightIndex));
47}