1function mergeSort(arr, lo = 0, hi = arr.length - 1) {
2 if (lo >= hi) return arr;
3 const mid = Math.floor((lo + hi) / 2);
4 mergeSort(arr, lo, mid);
5 mergeSort(arr, mid + 1, hi);
6 merge(arr, lo, mid, hi);
7 return arr;
8}
9function merge(arr, lo, mid, hi) {
10 const left = arr.slice(lo, mid + 1);
11 const right = arr.slice(mid + 1, hi + 1);
12 let i = 0, j = 0, k = lo;
13 while (i < left.length && j < right.length) {
14 if (left[i] <= right[j]) {
15 arr[k++] = left[i++];
16 } else {
17 arr[k++] = right[j++];
18 }
19 }
20 while (i < left.length) arr[k++] = left[i++];
21 while (j < right.length) arr[k++] = right[j++];
22}