Merge Sort

Algorithms
principle

Also known as: mergesort

Grade 9-12

View on concept map

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. Merge sort is one of the most efficient general-purpose sorting algorithms and is used in many language standard libraries.

Definition

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.

💡 Intuition

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

🎯 Core Idea

Merge sort guarantees O(n log n) performance regardless of input order.

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].

Formula

O(n \log n) time complexity

🌟 Why It 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).

💭 Hint When Stuck

To understand merge sort, focus on the merge step first: given two sorted lists, produce one sorted list by always picking the smaller front element. Then understand that recursion handles the splitting and sorting—a single-element list is already sorted (base case).

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 Stuck Point

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

⚠️ 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)

Frequently Asked Questions

What is Merge Sort in CS Thinking?

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.

What is the Merge Sort formula?

O(n \log n) time complexity

When do you use Merge Sort?

To understand merge sort, focus on the merge step first: given two sorted lists, produce one sorted list by always picking the smaller front element. Then understand that recursion handles the splitting and sorting—a single-element list is already sorted (base case).

How Merge Sort Connects to Other Ideas

To understand merge sort, you should first be comfortable with sorting, recursion and efficiency. Once you have a solid grasp of merge sort, you can move on to bubble sort and binary search.

← Back to Explorer