Merge Sort Visualization

What is Merge Sort?

Merge Sort is a divide-and-conquer algorithm that works by recursively dividing the input array into smaller subarrays until each subarray contains just one element, which is inherently sorted. The algorithm then merges these sorted subarrays back together in a way that produces the final sorted result. This visualization shows both the splitting and merging phases of merge sort.

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 proportional to the input size.

Array Size:
Current Array:
FastMediumSlow

No data to visualize

How Merge Sort Works

Merge Sort works in two main phases:

1. Splitting Phase

  1. Start with the complete unsorted array
  2. Divide the array into two halves (roughly equal size)
  3. Recursively divide each half into halves
  4. Continue until each subarray contains only one element
  5. Single-element arrays are inherently sorted

2. Merging Phase

  1. Start merging pairs of adjacent sorted subarrays
  2. Compare elements from both subarrays and merge in sorted order
  3. Continue merging larger subarrays until the entire array is sorted
  4. Each merge combines two sorted subarrays into a single sorted array

Merge Sort Implementation


// Merge Sort Algorithm
function mergeSort(array) {
  // Base case
  if (array.length <= 1) {
    return array;
  }
  
  // Split array into halves
  const middle = Math.floor(array.length / 2);
  const left = array.slice(0, middle);
  const right = array.slice(middle);
  
  // Recursively sort both halves
  return merge(
    mergeSort(left),
    mergeSort(right)
  );
}

// Merge two sorted arrays
function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  
  // Compare elements from both arrays and add smaller one to 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 remaining elements
  return result
    .concat(left.slice(leftIndex))
    .concat(right.slice(rightIndex));
}