Merge Sort

Merge Sort is a classic sorting algorithm that follows the divide-and-conquer strategy. It divides the input array into smaller sub-arrays, recursively sorts those sub-arrays, and then merges them back together to produce a sorted array. Merge Sort is known for its stability and predictable O(n log n) time complexity.

How Merge Sort Works

Merge Sort is a comparison-based sorting algorithm with a time complexity of O(n log n). It is particularly useful for large datasets and is a stable sorting algorithm, meaning it maintains the relative order of equal elements.

Algorithm Steps

1. Divide: Split the array into two halves.
2. Conquer: Recursively sort each half.
3. Merge: Combine the sorted halves to produce the final sorted array.

Pseudocode

Here’s the pseudocode for Merge Sort:

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    let result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    // Merge the two sorted arrays into one
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    // If there are remaining elements in the left array
    while (leftIndex < left.length) {
        result.push(left[leftIndex]);
        leftIndex++;
    }

    // If there are remaining elements in the right array
    while (rightIndex < right.length) {
        result.push(right[rightIndex]);
        rightIndex++;
    }

    return result;
}

// Example usage
const array = [3, 6, 8, 10, 1, 2, 1];
const sortedArray = mergeSort(array);
console.log(sortedArray);  // Output: [1, 1, 2, 3, 6, 8, 10]