mergeSort.js

function mergeSort(array) {
    if (array.length <= 1) {
        return array; // Base case: arrays with 0 or 1 elements are already sorted
    }

    const mid = Math.floor(array.length / 2); // Find the middle index
    const left = array.slice(0, mid); // Divide the array into two halves
    const right = array.slice(mid);

    // Recursively sort both halves and then merge them
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    let sortedArray = [];
    let i = 0;
    let j = 0;

    // Merge the two arrays into a single sorted array
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            sortedArray.push(left[i]);
            i++;
        } else {
            sortedArray.push(right[j]);
            j++;
        }
    }

    // If there are remaining elements in the left array, add them to the sorted array
    while (i < left.length) {
        sortedArray.push(left[i]);
        i++;
    }

    // If there are remaining elements in the right array, add them to the sorted array
    while (j < right.length) {
        sortedArray.push(right[j]);
        j++;
    }

    return sortedArray;
}

// Example usage:
const array = [7, 12, 4, 11, 3];
const sortedArray = mergeSort(array);
console.log(sortedArray); // Output: [3, 4, 7, 11, 12]