prep4place
Back to Visualizer

Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the array into halves, recursively sorts them, and then merges the sorted halves. It's stable and guarantees O(n log n) time.

Best: O(n log n)Avg: O(n log n)Space: O(n)
Size:20
Speed:50%
Default
Comparing
Swapping
Sorted
Pivot
Current
0
Comparisons
0
Swaps

How It Works

  1. 1Divide the array into two halves
  2. 2Recursively sort each half
  3. 3Merge the two sorted halves
  4. 4Compare elements from both halves
  5. 5Place smaller element first in merged array
  6. 6Continue until all elements are merged

Time Complexity

Best CaseO(n log n)
Average CaseO(n log n)
Worst CaseO(n log n)
Space ComplexityO(n)

Code

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

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