Runtime Complexity: O(n*log(n))
const mergeSort = (arr, low, high) => {
if (low < high) {
const mid = low + Math.floor((high - low) / 2);
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
};
const merge = (arr, low, mid, high) => {
const tempArr = [];
let i = low;
let j = mid + 1;
let k = 0;
while (i <= mid && j <= high) {
tempArr[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) {
tempArr[k++] = arr[i++];
}
while (j <= high) {
tempArr[k++] = arr[j++];
}
for (const val of tempArr) {
arr[low++] = val;
}
};
const arr = [4, -1, 1, 0, 3, 4];
mergeSort(arr, 0, arr.length - 1);
console.log(arr); // [-1, 0, 1, 3, 4, 4]