Merge Sort

Consistently efficient divide-and-conquer

Merge Sort is a legendary sorting algorithm that uses the Divide and Conquer strategy. It breaks down an array into single-element sub-arrays, then merges them back together in a sorted order. Unlike other basic sorts, its performance is always $O(n \log n)$.

Depth

Comparisons

Merges

Press "Start Sorting" to begin

Left Half

Right Half

Comparing

Merging

Fully Sorted

Speed

Divide & Conquer Analysis

Merge Sort is a stable sort that follows the principle of Merge: two sorted lists can be merged into a single sorted list in $O(n)$ time. By recursively splitting the unsorted list, we create a binary tree with $\log n$ levels of depth.

Logarithmic Depth

Because the array is halved at each step, there are exactly $\lceil \log_2(n) \rceil$ levels of recursion. This is why the log factor appears.

Space Overheads

Standard Merge Sort is not "in-place." It requires $O(n)$ extra space to store the temporary sub-arrays during the merge phase.

Complexity

Best Case$O(n \log n)$

Average Case$O(n \log n)$

Worst Case$O(n \log n)$

Space Complexity$O(n)$

Memory EfficiencyModerate

Logic Pattern

Pseudocode

TypeScript

1function mergeSort(arr) {
2  if (arr.length <= 1) return arr;
3  
4  const mid = arr.length / 2;
5  const left = mergeSort(arr.slice(0, mid));
6  const right = mergeSort(arr.slice(mid));
7  
8  return merge(left, right);
9}

Real World

Merge Sort is the backbone of Java's Arrays.sort() for objects and Python's Timsort (which is a hybrid of Merge and Insertion Sort).

Implementations

Python (Recursive)

Pseudocode

Python

1def merge_sort(arr):
2    if len(arr) <= 1:
3        return arr
4    
5    mid = len(arr) // 2
6    left = merge_sort(arr[:mid])
7    right = merge_sort(arr[mid:])
8    
9    return merge(left, right)
10 
11def merge(left, right):
12    result = []
13    i = j = 0
14    while i < len(left) and j < len(right):
15        if left[i] < right[j]:
16            result.append(left[i])
17            i += 1
18        else:
19            result.append(right[j])
20            j += 1
21    result.extend(left[i:])
22    result.extend(right[j:])
23    return result

High-Performance JS

Pseudocode

JavaScript

1function mergeSort(arr) {
2  if (arr.length <= 1) return arr;
3 
4  const mid = Math.floor(arr.length / 2);
5  const left = mergeSort(arr.slice(0, mid));
6  const right = mergeSort(arr.slice(mid));
7 
8  return merge(left, right);
9}
10 
11function merge(left, right) {
12  let result = [];
13  while (left.length && right.length) {
14    if (left[0] < right[0]) {
15      result.push(left.shift());
16    } else {
17      result.push(right.shift());
18    }
19  }
20  return [...result, ...left, ...right];
21}

Divide & Conquer Analysis

Logarithmic Depth

Because the array is halved at each step, there are exactly $\lceil \log_2(n) \rceil$ levels of recursion. This is why the log factor appears.

Space Overheads

Standard Merge Sort is not "in-place." It requires $O(n)$ extra space to store the temporary sub-arrays during the merge phase.

1function mergeSort(arr) { 2 if (arr.length <= 1) return arr; 3 4 const mid = arr.length / 2; 5 const left = mergeSort(arr.slice(0, mid)); 6 const right = mergeSort(arr.slice(mid)); 7 8 return merge(left, right); 9}

Implementations

Python (Recursive)

Pseudocode

Python

1def merge_sort(arr):
2    if len(arr) <= 1:
3        return arr
4    
5    mid = len(arr) // 2
6    left = merge_sort(arr[:mid])
7    right = merge_sort(arr[mid:])
8    
9    return merge(left, right)
10 
11def merge(left, right):
12    result = []
13    i = j = 0
14    while i < len(left) and j < len(right):
15        if left[i] < right[j]:
16            result.append(left[i])
17            i += 1
18        else:
19            result.append(right[j])
20            j += 1
21    result.extend(left[i:])
22    result.extend(right[j:])
23    return result

High-Performance JS

Pseudocode

JavaScript

1function mergeSort(arr) {
2  if (arr.length <= 1) return arr;
3 
4  const mid = Math.floor(arr.length / 2);
5  const left = mergeSort(arr.slice(0, mid));
6  const right = mergeSort(arr.slice(mid));
7 
8  return merge(left, right);
9}
10 
11function merge(left, right) {
12  let result = [];
13  while (left.length && right.length) {
14    if (left[0] < right[0]) {
15      result.push(left.shift());
16    } else {
17      result.push(right.shift());
18    }
19  }
20  return [...result, ...left, ...right];
21}