AlgoVerse

Merge sort

Split the array in half, sort each half recursively, then merge the two sorted halves.

Merge sort is the classic "divide and conquer" algorithm:

Read the full explanation ↓
Input:
n=8PDF export

Eight mixed numbers: three levels of splitting and seven merges.

  1. def merge_sort(a):
  2. sort(a, 0, len(a) - 1)
  3. return a
  6. def sort(a, lo, hi):
  7. if lo >= hi:
  8. return
  9. mid = (lo + hi) // 2
  10. sort(a, lo, mid)
  11. sort(a, mid + 1, hi)
  12. merge(a, lo, mid, hi)
  15. def merge(a, lo, mid, hi):
  16. left = a[lo:mid + 1]
  17. right = a[mid + 1:hi + 1]
  18. i = 0
  19. j = 0
  20. k = lo
  21. while i < len(left) and j < len(right):
  22. if left[i] <= right[j]:
  23. a[k] = left[i]
  24. i = i + 1
  25. else:
  26. a[k] = right[j]
  27. j = j + 1
  28. k = k + 1
  29. while i < len(left):
  30. a[k] = left[i]
  31. i = i + 1
  32. k = k + 1
  33. while j < len(right):
  34. a[k] = right[j]
  35. j = j + 1
  36. k = k + 1

Invariant: In the merge loop, a[lo..k−1] holds the smallest items of left and right, in order.

Start

5021427314352667

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

Orange = changed in this step

a list

52471326

Call stack

  1. merge_sort()line 1
Step 1 of 245
Black = split · Orange = key stepcompare: 0/17 · split: 0/7 · copy: 0/7 · write: 0/24

    How the work grows with input size

    Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • comparisons
    • write
    • current input (n=8)
    02040608046810121416n = number of itemswritecomparisons
    Show as a table
    ncomparisonswrite
    44.88
    69.716
    815.324
    1022.234
    1230.144
    1437.754
    1645.364
    Explanation

    The idea

    Merge sort is the classic "divide and conquer" algorithm:

    1. Divide: split the range a[lo..hi] in half at mid.
    2. Conquer: sort each half recursively with the same algorithm. A one-item range is already sorted.
    3. Combine: merge the two sorted halves.

    Merging

    The two halves are copied into left and right. At each step, one comparison finds the smallest remaining item of the two sides, and it is written to a[k]. When one side runs out, the rest of the other side is copied without comparing.

    Cost

    • The recursion is log n levels deep and each level merges the whole array once, so the time is O(n log n) in every case.
    • Merging needs a helper array, so the extra memory is O(n).
    • The number of comparisons depends on the input: for 8 items it is between 12 (already sorted) and 17 (an interleaved input).

    Stability

    With the test left[i] ≤ right[j], of two equal items the one from the left half is always written first, so equal items keep their order and the sort is stable.

    What to watch in the trace

    • The blue band behind the bars is the range lo..hi of the running call.
    • The "recursion tree" under the picture shows which subproblem is running and which are finished.
    • Use the "every loop round" detail level to see only the splits, and "every operation" to follow a merge comparison by comparison.