FlowLab Logo

Merge Sort Visualizer

SlowFast
520
(8)
55
[0]
18
[1]
90
[2]
60
[3]
65
[4]
73
[5]
13
[6]
14
[7]
Splitting
Merging
Comparing
Operation Logs
No operations yet
Algorithm Info
Time Complexity: O(n log n) for all cases
Space Complexity: O(n) - requires additional memory for temporary arrays
Stable: Yes - maintains relative order of equal elements
Divide & Conquer: Recursively divides array into halves, then merges sorted subarrays
Guarantee: Always O(n log n) performance regardless of input
Use case: Excellent for large datasets requiring guaranteed performance
Implementation
function mergeSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;
  
  const mid = Math.floor((left + right) / 2);
  
  // Divide: recursively sort left and right halves
  mergeSort(arr, left, mid);
  mergeSort(arr, mid + 1, right);
  
  // Conquer: merge the sorted halves
  merge(arr, left, mid, right);
}

function merge(arr, left, mid, right) {
  // Create temporary arrays
  const leftArr = arr.slice(left, mid + 1);
  const rightArr = arr.slice(mid + 1, right + 1);
  
  let i = 0, j = 0, k = left;
  
  // Merge back into original array
  while (i < leftArr.length && j < rightArr.length) {
    if (leftArr[i] <= rightArr[j]) {
      arr[k] = leftArr[i];
      i++;
    } else {
      arr[k] = rightArr[j];
      j++;
    }
    k++;
  }
  
  // Copy remaining elements
  while (i < leftArr.length) {
    arr[k] = leftArr[i];
    i++;
    k++;
  }
  
  while (j < rightArr.length) {
    arr[k] = rightArr[j];
    j++;
    k++;
  }
}