What is the time complexity of merge sort?

Best case O(n log n). Average case O(n log n). Worst case O(n log n). Space complexity is O(n). log n levels of recursion, each doing O(n) merging work.

Merge sort

medium

Nothing happens on the way down - all the work is in the merges on the way up. O(n log n) in every case including adversarial input, which is a guarantee quicksort cannot make.

Best O(n log n)Average O(n log n)Worst O(n log n)Space O(n)StableNeeds extra memory

Loading the merge sort engine…

Where to go next

Quick sort

medium

Partition around a pivot, then recurse on both halves.

Heap sort

medium

Build a heap in the array, then extract the maximum n times.

Recursion and the call stack

easy

Watch fib(n) build an exponential tree, then memoise it away.