Key Concepts

Review core concepts you need to learn to master this subject

Merge Sort Merging

Big-O Runtime for Merge Sort

Merge Sort Implementation in Python

Merge Sort Merging

Merge Sort is a divide and conquer algorithm. It consists of two parts:

1) splitting the original list into smaller sorted lists recursively until there is only 1 element in the list,
2) merging back the presorted 1-element lists into 2-element lists, 4-element lists, and so on recursively.

The merging portion is iterative and takes 2 sublists. The first element of the left sublist is compared to the first element of the right sublist. If it is smaller, it is added to a new sorted list, and removed from the left sublist. If it is bigger, the first element of the right sublist is added instead to the sorted list and then removed from the right sublist. This is repeated until either the left or right sublist is empty. The remaining non-empty sublist is appended to the sorted list.

Merge Sort: Conceptual
Lesson 1 of 2
  1. 1
    What Is A Merge Sort?
    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…
    Start
  2. 2
    How To Merge Sort:
    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…
    Start
  3. 3
    Merging
    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…
    Start
  4. 4
    Merge Sort Performance
    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…
    Start

How you'll master it

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

Pro Logo