SESKStuff Everyone Should Know
SESK: Stuff Everyone Should Know · sesk.info/tech-merge-sort-n-log-n

Merge sort splits a list in half, sorts each half, then merges. What is its running time?

O(n log n): log n levels of splitting, n work to merge at each level.

Start playing free

  1. O(n log n) ✔
  2. O(n²)
  3. O(n)

Why: You can only halve n items about log n times. At every level of halving, merging the sorted pieces back together touches all n items once, so the total is n times log n.

Huh, didn't know that: Merge sort is not in place: the simple version needs extra memory about the size of the list to do its merging.

The dad joke
Merge sort solves every problem the same way: split it in half and let someone smaller deal with it.
Like this card?
Play the game

References

Answer: O(n log n). You can only halve n items about log n times. At every level of halving, merging the sorted pieces back together touches all n items once, so the total is n times log n.

  1. MIT 6.006 Introduction to Algorithms, Lecture 3: Sorting ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec3
    Recursively sort first half and second half ... Merge sorted halves into one sorted list ... Guess T(n) = Θ(n log n)
    Checked 2026-10-10.

Think this answer is wrong? Tap "Challenge this answer" on the card in the game and tell us why.

Test yourself in the game

Tech & GadgetsWhat must be true about a list before you can use binary search on it?Tech & GadgetsWhat is the worst-case running time of insertion sort on n items?Tech & GadgetsWhat does it mean that a sorting algorithm is stable?

That's stuff everyone should know.