A+DS

Merge Sort

Divide and conquer: split, sort, merge.

Imagine tearing a phone book in half, then tearing each half in half, until you have single pages. Then merge pairs of pages back together in order. Merge Sort splits the array recursively until each piece has one element, then merges them back in sorted order.

      [ ? ? ? ? ? ? ? ? ]      full array
       /                \
   [ ? ? ? ? ]    [ ? ? ? ? ]    split
    /      \        /      \
  [? ?]  [? ?]  [? ?]  [? ?]    split again

  [✔ ✔]  [✔ ✔]  [✔ ✔]  [✔ ✔]    merge pairs
      [✔ ✔ ✔ ✔]    [✔ ✔ ✔ ✔]    merge again
          [✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔]      done!

How it works

  1. 1Split the array in half recursively
  2. 2Keep splitting until each piece has 1 element
  3. 3Merge pairs back together in sorted order
  4. 4Each merge combines two sorted halves into one sorted whole

Loading...