Merge Sort Formula

Merge sort is a divide-and-conquer sorting algorithm that splits a list in half, recursively sorts each half, then merges the two sorted halves back together in order.

The Formula

O(nlog⁡n) time complexity

Ask yourself: Is a list sorted by splitting it in half, sorting each half, then merging the sorted halves?

Quick example

[5,3,1,4] → split to [5,3] and [1,4] → sort to [3,5] and [1,4] → merge to [1,3,4,5].

What this formula means

A divide-and-conquer sorting algorithm that splits a list in half, recursively sorts each half, then merges the two sorted halves back together in order. The key insight is that merging two already-sorted lists into one sorted list is efficient and straightforward.

Merge sort is like sorting a tall stack of exam papers with a group of friends: keep halving the stack and passing halves on until each person holds a single paper, which is already sorted. Then pairs of people combine their piles by repeatedly taking the lower-scoring of the two top papers, until one sorted stack is left. A program does the passing on with recursion.

Formal view

Merge sort divides array A[0..n−1] into A[0..m−1] and A[m..n−1] where m=⌊n/2⌋, recursively sorts each half, and merges in O(n) time. Total: T(n)=2T(n/2)+O(n)=O(nlog⁡n).

Worked examples

Example 1

medium
Run merge sort on [5,2,4,1]. Show the result after each phase.
Show solution

Answer

[1,2,4,5]

First step

1.
Split: [5,2] and [4,1].

See the full worked solution + why-it-works coaching

SetupKey insightWhy it worksCommon pitfallConnection

Free: full solutions on 3 topics a day. No card.

Every topic, every day: the Family plan

Example 2

medium
Merge [2,5,8,10] and [1,3,6,9]. Give the result.

Example 3

medium
Merge sort [8,3,7,5]. Show splits and final result.

Common mistakes

  • Forgetting that merge sort requires O(n) extra memory for the temporary arrays during merging
  • Incorrectly implementing the merge step by not handling the case when one half is exhausted before the other
  • Confusing merge sort's guaranteed O(nlog⁡n) with quicksort's average O(nlog⁡n) but worst-case O(n2)

Why this formula matters

Merge sort turns sorting from O(n2) into O(nlog⁡n), and it guarantees that speed on every input, sorted, reversed or random. For a million items that is about 20 million comparisons instead of about 500 billion. It is stable, so it suits sorting records by several fields, and its merge step is how databases sort files too big for memory. The price is memory: merging needs a second array as large as the input.

Frequently asked questions

What is the Merge Sort formula?

A divide-and-conquer sorting algorithm that splits a list in half, recursively sorts each half, then merges the two sorted halves back together in order. The key insight is that merging two already-sorted lists into one sorted list is efficient and straightforward.

How do you use the Merge Sort formula?

Use merge sort for large lists, when you need a guaranteed O(nlog⁡n) running time, when the sort must be stable (equal items keep their order), or when the data is too big for memory and must be sorted in chunks and merged. For a tiny or nearly sorted list, a simple method such as insertion sort can be faster in practice. If memory is very tight, an in-place method such as heapsort avoids merge sort's extra array.

Why is the Merge Sort formula important in CS Thinking?

Merge sort turns sorting from O(n2) into O(nlog⁡n), and it guarantees that speed on every input, sorted, reversed or random. For a million items that is about 20 million comparisons instead of about 500 billion. It is stable, so it suits sorting records by several fields, and its merge step is how databases sort files too big for memory. The price is memory: merging needs a second array as large as the input.

What do students get wrong about Merge Sort?

Merge sort uses extra memory proportional to the input size (unlike in-place sorts).

What should I learn before the Merge Sort formula?

Before studying the Merge Sort formula, you should understand: sorting, recursion, efficiency.