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.

The Formula

O(nlog⁡n)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]A[0..n-1] into A[0..m]A[0..m] and A[m+1..n−1]A[m+1..n-1] where m=⌊n/2⌋m = \lfloor n/2 \rfloor, recursively sorts each half, and merges in O(n)O(n) time. Total: T(n)=2T(n/2)+O(n)=O(nlog⁡n)T(n) = 2T(n/2) + O(n) = O(n \log n).

Worked Examples

Example 1

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

Answer

[1,2,4,5][1, 2, 4, 5]

First step

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

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

SetupKey insightWhy it worksCommon pitfallConnection

Unlock answer keys One Family plan — every worked solution, all subjects

Example 2

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

Example 3

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

Common Mistakes

  • Forgetting that merge sort requires O(n)O(n) extra memory for the temporary arrays during merging - Fix this by naming the input, process, output, evidence, and checking "Am I judging the steps of a method for correctness, termination, edge cases, and efficiency as inputs change?" before using the concept.
  • Incorrectly implementing the merge step by not handling the case when one half is exhausted before the other - Fix this by naming the input, process, output, evidence, and checking "Am I judging the steps of a method for correctness, termination, edge cases, and efficiency as inputs change?" before using the concept.
  • Confusing merge sort's guaranteed O(nlog⁡n)O(n \log n) with quicksort's average O(nlog⁡n)O(n \log n) but worst-case O(n2)O(n^2) - Fix this by naming the input, process, output, evidence, and checking "Am I judging the steps of a method for correctness, termination, edge cases, and efficiency as inputs change?" before using the concept.
  • Using merge sort from a keyword alone - Signal words like algorithm, search, sort only point to a possible model; the computing structure must match too.

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(nlog⁡n)O(n \log n) worst-case performance makes it reliable for any input, unlike quicksort which can degrade to O(n2)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(nlog⁡n)O(n \log n) worst-case performance makes it reliable for any input, unlike quicksort which can degrade to O(n2)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 See All Examples Practice Problems