Merge sort is one of the three solid sort algorithms. (The other two are heap sort and (randomized) quick sort.)
Merge sort is the sort analogue of binary search - we sort by continually splitting the array of data in half, until we reach the trivial case of an array with a single piece of data in it. Each recursive instance of merge sort then has a single piece of data, and these functions begin to merge their sorted results together.
Because the continual splitting in half is O(log n) per step, for O(n log n) overall, and because the merge operation is linear, O(n), we can use the Master Theorem to prove a stronger result than O(n log n). We can show:
See Algorithm Analysis/Merge Sort for the Master Theorem analysis of merge sort.
AlgorithmsPart of Computer Science Notes
Series on Algorithms
Algorithm Practice and Writeups
Flags · Template:AlgorithmsFlag · e