Merge Sort Formula

The Formula

O(n \log n) time complexity

When to use: Split a messy deck of cards in half, sort each half, then interleave them back in order.

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.

Split a messy deck of cards in half, sort each half, then interleave them back in order.

Formal View

Merge sort divides array A[0..n-1] into A[0..m] and A[m+1..n-1] where m = \lfloor n/2 \rfloor, recursively sorts each half, and merges in O(n) time. Total: T(n) = 2T(n/2) + O(n) = O(n \log n).

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(n \log n) with quicksort's average O(n \log n) but worst-case O(n^2)

Why This Formula Matters

Merge sort is one of the most efficient general-purpose sorting algorithms and is used in many language standard libraries. Its guaranteed O(n \log n) worst-case performance makes it reliable for any input, unlike quicksort which can degrade to O(n^2).

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?

Split a messy deck of cards in half, sort each half, then interleave them back in order.

Why is the Merge Sort formula important in CS Thinking?

Merge sort is one of the most efficient general-purpose sorting algorithms and is used in many language standard libraries. Its guaranteed O(n \log n) worst-case performance makes it reliable for any input, unlike quicksort which can degrade to O(n^2).

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.

← Back to Merge Sort