Key Concepts

Review core concepts you need to learn to master this subject

Big-O Runtime for Merge Sort

The Merge Sort algorithm is divided into two parts. The first part repeatedly splits the input list into smaller lists to eventually produce single-element lists. The best, worst and average runtime for this part is Θ(log N). The second part repeatedly merges and sorts the single-element lists to twice its size until the original input size is achieved. The best, worst and average runtime for this part is Θ(N). Therefore, the combined runtime is Θ(N log N).

Merge Sort: Conceptual
Lesson 1 of 2
  1. 1
    Merge sort is a sorting algorithm created by John von Neumann in 1945. Merge sort’s “killer app” was the strategy that breaks the list-to-be-sorted into smaller parts, sometimes called a _divide-an…
  2. 2
    Merge sorting takes two steps: splitting the data into “runs” or smaller components, and the re-combining those runs into sorted lists (the “merge”). When splitting the data, we divide the input t…
  3. 3
    When merging larger pre-sorted lists, we build the list similarly to how we did with single-element lists. Let’s call the two lists left and right. Both left and right are already sorted. We want…
  4. 4
    Merge sort was unique for its time in that the best, worst, and average time complexity are all the same: Θ(N*log(N)). This means an almost-sorted list will take the same amount of time as a comple…

How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory

Pro Logo