Merge Sort Visualizer

How Merge Sort Works

Merge Sort is a divide-and-conquer algorithm that works by:

1. Dividing the unsorted list into n sublists, each containing one element
2. Repeatedly merging sublists to produce new sorted sublists until there is only one sublist remaining

Algorithm Steps:

function mergeSort(array) {
    if (array.length <= 1) return array;
    
    const middle = Math.floor(array.length / 2);
    const left = array.slice(0, middle);
    const right = array.slice(middle);
    
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    let result = [];
    let leftIndex = 0;
    let rightIndex = 0;
    
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }
    
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
        

Time Complexity:

Case	Time Complexity
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n log n)

Space Complexity:

O(n) - Requires additional space for the temporary arrays