Merge Sort

1function mergeSort(arr) {
2  // Base case: arrays of length 0 or 1 are already sorted
3  if (arr.length <= 1) return arr;
4 
5  const mid = Math.floor(arr.length / 2);
6  const left = mergeSort(arr.slice(0, mid));
7  const right = mergeSort(arr.slice(mid));
8 
9  return merge(left, right);
10}
11 
12function merge(left, right) {
13  const result = [];
14  let l = 0;
15  let r = 0;
16 
17  // Compare elements from left and right arrays
18  while (l < left.length && r < right.length) {
19    if (left[l] <= right[r]) {
20      result.push(left[l]);
21      l++;
22    } else {
23      result.push(right[r]);
24      r++;
25    }
26  }
27 
28  // Append any remaining elements
29  while (l < left.length) {
30    result.push(left[l]);
31    l++;
32  }
33  while (r < right.length) {
34    result.push(right[r]);
35    r++;
36  }
37 
38  return result;
39}
40 
41// Example usage:
42// mergeSort([38, 27, 43, 3, 9, 82, 10]); // [3, 9, 10, 27, 38, 43, 82]