Divide & Conquer Visualization: Merge Sort

Interactive Merge Sort

Visualize the Merge Sort algorithm, a classic example of Divide and Conquer.

Initial Array (comma-separated):

Speed: 500ms

Enter an array and click 'Start Sort' to begin.

How Merge Sort Works

Merge Sort follows the Divide and Conquer paradigm:

Divide: If the array has more than one element, divide it recursively into two halves (left and right) until each subarray contains only one element (which is inherently sorted).
Conquer: Recursively sort the two subarrays using Merge Sort.
Combine: Merge the two sorted subarrays back into a single sorted array. This merge step involves comparing elements from both subarrays and placing the smaller element into the resulting array, repeating until all elements from both subarrays are merged.

Time Complexity: O(n log n) in all cases (worst, average, best). The dividing step takes O(log n) levels of recursion, and the merging step at each level takes O(n) time.
Space Complexity: O(n) because it typically requires an auxiliary array of size n to store the merged results during the combine step.

Example Implementation (Conceptual)

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr; // Base case: array is already sorted
    }

    // Divide
    const mid = Math.floor(arr.length / 2);
    const leftHalf = arr.slice(0, mid);
    const rightHalf = arr.slice(mid);

    // Conquer (Recursive calls)
    const sortedLeft = mergeSort(leftHalf);
    const sortedRight = mergeSort(rightHalf);

    // Combine (Merge)
    return merge(sortedLeft, sortedRight);
}

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

    // Compare elements and add the smaller one to the result
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    // Add any remaining elements from left or right subarray
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}