Merge Sort Visualizer: Step-by-Step Animation & Complexity

Merge Sort

Category: Sorting | Time: O(n log n) | Space: O(n)

Input Data

Visualization

Visual representation of the data structure

About Merge Sort

An efficient, stable, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945. The algorithm splits the array into two halves, recursively sorts them, and then merges the two sorted halves.

Code Editor

The code is for reference. Editing it won't affect the visualization.

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) {
  let resultArray = [], leftIndex = 0, rightIndex = 0;
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      resultArray.push(left[leftIndex]);
      leftIndex++;
    } else {
      resultArray.push(right[rightIndex]);
      rightIndex++;
    }
  }
  return resultArray
    .concat(left.slice(leftIndex))
    .concat(right.slice(rightIndex));
}

Variable State

{
  "arr": "[38,27,43,3,9,82,10]"
}

Merge Sort: How It Works

Last updated October 28, 2026

Overview

Merge Sort is the classic divide-and-conquer sort. It splits the array in half, sorts each half recursively, and then merges the two sorted halves into one sorted run. An array of length one is already sorted, which ends the recursion.

All of the real work happens in the merge step. Two pointers walk the left and right halves; at each step the smaller front element is copied to the output. Because each level of recursion touches every element once and there are log2(n) levels, the total cost is O(n log n) for every input.

With the default input 38, 27, 43, 3, 9, 82, 10, the visualizer first drills down to single elements such as [38] and [27], then merges them back up: [27, 38], [3, 27, 38, 43], and finally the full sorted array.

Step by step

If the current range has one element or fewer, return — it is sorted.
Find the middle index m and recursively sort l..m and m+1..r.
Copy the two halves into temporary arrays L and R.
Repeatedly copy the smaller of L[i] and R[j] back into the array, advancing that pointer.
When one half runs out, copy whatever remains of the other half.

Complexity

Case	Cost	Why
Best case	O(n log n)	The split-and-merge structure does not depend on input order.
Average case	O(n log n)	log2(n) levels, each doing O(n) merge work.
Worst case	O(n log n)	Guaranteed — no bad pivot problem as in Quick Sort.
Extra space	O(n)	The temporary arrays used while merging.

When to use it

When you need a guaranteed O(n log n) and a stable sort, e.g. sorting records by a secondary key.
Sorting linked lists, where merging needs no extra array and random access is unavailable.
External sorting of data too large for memory: sort chunks, then merge them from disk.

Common mistakes

Using < instead of <= when comparing L[i] and R[j] takes equal elements from the right first and makes the sort unstable.
Computing the middle as (l + r) / 2 can overflow in fixed-width integer languages; l + (r - l) / 2 is safe.
Allocating new temporary arrays on every call is a common performance trap; production code allocates one buffer up front.

Worked Example: Merge Sort Dry Run

Generated from the same trace that drives the visualizer above, using the default input.

A dry run is the best way to check your understanding of Merge Sort: follow each row, predict the next one, and compare. The run below takes 138 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.

Input: 38, 27, 43, 3, 9, 82, 10
Result: return value = [3, 9, 10, 27, 38, 43, 82]

Step	Line	Array	What happens
1	1	[38, 27, 43, 3, 9, 82, 10]
2	2	[38, 27, 43, 3, 9, 82, 10]	condition = 7 <= 1
6	2	[38, 27, 43, 3, 9, 82, 10]	condition = 4 <= 1
10	2	[38, 27, 43, 3, 9, 82, 10]	condition = 2 <= 1
14	2	[38, 27, 43, 3, 9, 82, 10]	condition = 1 <= 1
18	2	[38, 27, 43, 3, 9, 82, 10]	condition = 1 <= 1
23	13	[38, 27, 43, 3, 9, 82, 10]	left = [38], right = [27], condition = 38 < 27
25	18	[27, 27, 43, 3, 9, 82, 10]	resultArray = [27], rightIndex = 0
28	25	[27, 38, 43, 3, 9, 82, 10]	resultArray = [27,38]
31	2	[27, 38, 43, 3, 9, 82, 10]	condition = 2 <= 1
35	2	[27, 38, 43, 3, 9, 82, 10]	condition = 1 <= 1
39	2	[27, 38, 43, 3, 9, 82, 10]	condition = 1 <= 1
44	13	[27, 38, 43, 3, 9, 82, 10]	left = [43], right = [3], condition = 43 < 3
46	18	[27, 38, 3, 3, 9, 82, 10]	resultArray = [3], rightIndex = 0
49	25	[27, 38, 3, 43, 9, 82, 10]	resultArray = [3,43]
53	13	[27, 38, 3, 43, 9, 82, 10]	left = [27,38], right = [3,43], condition = 27 < 3
55	18	[3, 38, 3, 43, 9, 82, 10]	resultArray = [3], rightIndex = 0
57	13	[3, 38, 3, 43, 9, 82, 10]	left = [27,38], right = [3,43], condition = 27 < 43
59	15	[3, 27, 3, 43, 9, 82, 10]	resultArray = [3,27], leftIndex = 0
61	13	[3, 27, 3, 43, 9, 82, 10]	left = [27,38], right = [3,43], condition = 38 < 43
63	15	[3, 27, 38, 43, 9, 82, 10]	resultArray = [3,27,38], leftIndex = 1
69	2	[3, 27, 38, 43, 9, 82, 10]	condition = 3 <= 1
73	2	[3, 27, 38, 43, 9, 82, 10]	condition = 2 <= 1
77	2	[3, 27, 38, 43, 9, 82, 10]	condition = 1 <= 1
81	2	[3, 27, 38, 43, 9, 82, 10]	condition = 1 <= 1
86	13	[3, 27, 38, 43, 9, 82, 10]	left = [9], right = [82], condition = 9 < 82
94	2	[3, 27, 38, 43, 9, 82, 10]	condition = 1 <= 1
99	13	[3, 27, 38, 43, 9, 82, 10]	left = [9,82], right = [10], condition = 9 < 10
103	13	[3, 27, 38, 43, 9, 82, 10]	left = [9,82], right = [10], condition = 82 < 10
105	18	[3, 27, 38, 43, 9, 10, 10]	resultArray = [9,10], rightIndex = 0
108	25	[3, 27, 38, 43, 9, 10, 82]	resultArray = [9,10,82]
112	13	[3, 27, 38, 43, 9, 10, 82]	left = [3,27,38,43], right = [9,10,82], condition = 3 < 9
116	13	[3, 27, 38, 43, 9, 10, 82]	left = [3,27,38,43], right = [9,10,82], condition = 27 < 9
118	18	[3, 9, 38, 43, 9, 10, 82]	resultArray = [3,9], rightIndex = 0
120	13	[3, 9, 38, 43, 9, 10, 82]	left = [3,27,38,43], right = [9,10,82], condition = 27 < 10
122	18	[3, 9, 10, 43, 9, 10, 82]	resultArray = [3,9,10], rightIndex = 1
124	13	[3, 9, 10, 43, 9, 10, 82]	left = [3,27,38,43], right = [9,10,82], condition = 27 < 82
126	15	[3, 9, 10, 27, 9, 10, 82]	resultArray = [3,9,10,27], leftIndex = 1
128	13	[3, 9, 10, 27, 9, 10, 82]	left = [3,27,38,43], right = [9,10,82], condition = 38 < 82
130	15	[3, 9, 10, 27, 38, 10, 82]	resultArray = [3,9,10,27,38], leftIndex = 2

The remaining 3 key steps follow the same pattern. Press play in the visualizer to watch every step through to the result.

Frequently Asked Questions

About Merge Sort

How does Merge Sort work?

Merge Sort is a classic divide-and-conquer algorithm. It works by recursively dividing the unsorted list into n sublists, each containing one element. Then, it repeatedly merges these sublists to produce new sorted sublists until there is only one sublist remaining, which is the final sorted list.

What is the time complexity of Merge Sort?

Merge Sort has a consistent time complexity of O(n log n) in all cases—best, average, and worst. This reliability is one of its main strengths.

What is the space complexity of Merge Sort?

The typical implementation of Merge Sort has a space complexity of O(n) because it requires an auxiliary array of the same size as the input to store the merged results during the merging phase.

Is Merge Sort a stable algorithm?

Yes, Merge Sort is a stable sorting algorithm. During the merge step, if two elements are equal, the element from the left sub-array is placed first, preserving the original relative order.

Is Merge Sort an external sorting algorithm?

Yes, Merge Sort is highly effective for external sorting, where the data to be sorted is too large to fit into memory. Its sequential access pattern (reading and writing large blocks of data) is ideal for working with slower media like hard drives.

What is the 'merge' step in Merge Sort?

The merge step is the core of the algorithm. It takes two sorted sub-arrays and combines them into a single sorted array. It does this by iterating through both sub-arrays with two pointers, and at each step, it copies the smaller of the two elements into the result array.

Can Merge Sort be done in-place?

While it's theoretically possible to perform an in-place merge, it is extremely complex and not practical, as it would lose the simplicity and efficiency of the standard algorithm. Therefore, almost all practical implementations use O(n) extra space.

How does Merge Sort compare to Quick Sort?

Merge Sort has a better worst-case time complexity (O(n log n) vs Quick Sort's O(n^2)), is stable, and is better for external sorting. However, Quick Sort is often faster in practice for in-memory arrays due to lower constant factors and better cache performance.

What is a bottom-up Merge Sort?

A bottom-up (or iterative) Merge Sort avoids recursion. It starts by merging pairs of single elements, then merges pairs of 2-element runs, then 4-element runs, and so on, until the entire array is sorted. It achieves the same O(n log n) time complexity.

Is Merge Sort a comparison-based sort?

Yes, Merge Sort is a comparison-based sorting algorithm because it relies on comparing elements to determine their order during the merge step.

Where can I learn more?

You can find a more detailed explanation on GeeksforGeeks.

Merge Sorted Arrays

From: Meta

View Question

Merge Intervals

From: Netflix

View Question