Merge-sort is a sorting algorithm. It takes as input an array whose values are in an arbitrary order and it outputs an array with the same elements in increasing order of values.
Example 1.
Input:
a = 7 2 6 4 3 8 9
Output:
2 3 4 6 7 8 9Why is merge-sort interesting?
- Merge-sort is interesting because it has a guaranteed worst-case run-time of O(n log n), which is the best that can be achieved by comparison-based sorting algorithms.
- Merge-sort is cache friendly, unlike other sorting algorithms with a guaranteed run-time of O(n log n), such as heap-sort. Being cache-friendly makes it much faster on modern computers, which have large ammount of cache memory.
- Merge-sort is a very nice example of a recursive algorithm, with a fascinating sub-algorithm used for… merging.
- Merge-sort is used in practice. For example, the C library function qsort implements, unlike its name suggests, merge-sort. Also, tuned top-notch real-world implementions of sorting, such as Tim-sort, use merge-sort under the hood in various places.
The only downside to merge-sort that I can think of is that it is not usually in-place: it uses additional memory for processing in the form of a temporary array or two. If you would like to learn about an in-place algorithm with a time complexity of Θ(n log₂(n)) on average, check out our tutorial on Quicksort.
Page 1 – Introduction
Page 2 – How it Works
Page 3 – Implementation
Page 4 – Time Complexity