Merge Sort Algorithm

The merge sort algorithm is a divide-and-conquer sort: split the list in half, sort each half, then merge the two sorted halves. It guarantees O(n log n) time and keeps equal items in order, which is why it sits at the heart of many library sorts. Step through it below, then read how it works.

What is Merge Sort?

Merge Sort is a divide-and-conquer algorithm. It splits the list in half, sorts each half recursively, and then merges the two sorted halves into one sorted list.

Key insight: Merging two sorted lists is cheap: just compare the front elements and take the smaller one. Because the list is halved each time, there are only about log n levels of merging, each costing O(n).

Merge Sort Time Complexity

Measure	Value
Best case	O(n log n)
Average case	O(n log n)
Worst case	O(n log n)
Space	O(n)
Stable	Yes

For a formal definition and complexity analysis, see the NIST Dictionary of Algorithms and Data Structures entry for merge sort.

Algorithm Steps

1. If the list has 0 or 1 elements, it is already sorted.
2. Split the list into a left half and a right half.
3. Recursively sort both halves.
4. Merge the halves: repeatedly take the smaller front element.
5. Copy any leftover elements and return the merged list.

Advantages and Disadvantages

Advantages

• Guaranteed O(n log n) in the best, average and worst case
• Stable
• Works well with linked lists and data on disk
• Easy to parallelise

Disadvantages

• Needs O(n) extra memory
• Slower than Quick Sort in practice for small arrays because of copying
• Recursive implementation uses stack space

Real-World Applications

• Sorting very large data sets, including external sorting of files bigger than memory
• Sorting linked lists (no random access needed)
• Stable sorting is required, for example sorting records by several keys
• Basis of Timsort used by Python and Java for objects

When to Use Merge Sort

Choose it when you need guaranteed O(n log n) performance or a stable sort, or when data does not fit in memory.

Merge Sort Implementation

Python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= keeps the sort stable
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

JavaScript

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++]);   // <= keeps it stable
    else result.push(right[j++]);
  }
  return result.concat(left.slice(i), right.slice(j));
}

FAQ

Why is merge sort O(n log n)?

Halving the list repeatedly creates about log₂ n levels of recursion, and merging all the pieces on one level touches each element once, costing O(n). That gives O(n log n) in the best, average and worst case.

Is merge sort stable?

Yes, as long as the merge takes from the left half when two front elements are equal (the <= in the code below). That keeps equal items in their original order.

Merge sort vs quick sort: which should I use?

Merge sort guarantees O(n log n) and is stable, but needs O(n) extra memory. Quick Sort sorts in place and is usually faster in memory, but can degrade to O(n²) with bad pivots and is not stable.

---

More Sorting Algorithms

• Quick Sort
• Heap Sort
• Timsort
• Insertion Sort