Merge Sort

Overview

Merge sort is one of the three solid $ \Theta( n \log{n})</math sort algorithms. (The other two are heap sort and (randomized) quick sort.) ==Brief Description== 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. ==Algorithm Analysis== 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: <math> T(n) = \Theta \left( n \log{n} \right) $

See Algorithm Analysis/Merge Sort for the Master Theorem analysis of merge sort.