TRT
Sign in

Core · Module 8 · Lesson 2 of 5

Merge sort

Split the array in half, sort each half, merge the two sorted halves. Every level of splitting costs O(n) and there are log n levels, so merge sort is O(n log n) on every input, and it is stable.

Pro — members onlyAbout 14 minutes

By the end you can

  • Trace merge sort's splitting and merging, and implement the merge
  • Derive O(n log n) from the recursion tree, and explain the O(n) extra memory
  • Explain how external merge sort sorts data far larger than memory

Builds on Insertion and selection sort, Base cases and recursion trees.

01 · A question first

A database has to sort 100 GB of rows on a machine with 8 GB of memory. Merge sort handles it with a few sequential passes over the disk. How does sorting small pieces and merging them scale so far beyond what fits in memory?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Divide and conquer
  • The merge
  • Why it is O(n log n)
  • The cost: extra memory
  • Sorting more data than fits in memory
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeSort listSort a linked list in O(n log n) time with merge sort, splitting at the middle with fast and slow pointers and merging by rewiring nodes.Practice · medium · LeetCodeSort an arraySort an array of integers in O(n log n) without the built-in sort: implement merge sort, then quick sort with a random pivot, and compare.

Asked in interviews

Something wrong with this lesson? Report a problem