Skip to content
BENIBIX Learn

Merge Sort

Development🧮 Algorithms & Data StructuresSorting Algorithms

Also known as Mergesort

A sort that splits the list in halves, sorts them, then merges them back.

Think of it like

Think of it like two piles of cards. Sort each pile, then join them in order.

Example

Lucy merge-sorts 8 numbers. They split into 8 single items, then merge into pairs, fours and one sorted list of 8.

Why it matters

Its speed never gets bad, and it keeps equal items in their first order. Many built-in sorts use its ideas.

Definition

Merge sort splits a list in half, sorts each half, then merges the two halves. It keeps splitting until each piece has one item, which is already sorted. Merging two sorted lists is quick, because you only compare their front items. It always takes O(n log n) steps, even in the worst case. It needs extra memory the size of the list.

Common mistake

Forgetting the extra memory. On a huge list, the copy it needs can be too big.

Key takeaways

  1. 1
    Split, sort, merge. Again and again.
  2. 2
    Always O(n log n). No bad case.
  3. 3
    Needs extra memory. About the list's size.

Compare