function mergeSort(arr) {
if (arr.length <= 1) return arr;
// Split the array into two halves
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
// Merge the sorted halves
return merge(left, right);
}
function merge(left, right) {
let sortedArray = [];
let i = 0, j = 0;
// Merge the two sorted arrays
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
sortedArray.push(left[i]);
i++;
} else {
sortedArray.push(right[j]);
j++;
}
}
// Copy remaining elements from left (if any)
while (i < left.length) {
sortedArray.push(left[i]);
i++;
}
// Copy remaining elements from right (if any)
while (j < right.length) {
sortedArray.push(right[j]);
j++;
}
return sortedArray;
}
// Example usage
const array = [1, 7, 2, 8, 3, 5, 6];
const sortedArray = mergeSort(array);
console.log(sortedArray); // Output: [1, 2, 3, 5, 6, 7, 8]
