Fri Apr 23 2021
A natural approach to problem solving is divide and conquer. In terms of sorting, a simple way to do this would be to split the list in half, sort the halves, and then merge the sorted halves together. This is the idea behind Merge sort.
Merge sort is one of the simplest sorting algorithms conceptually, and has good performance both in the asymptotic sense and in empirical running time. Surprisingly, even though it is based on a simple concept, it is relatively difficult to implement in practice.
In sorting n objects, merge sort has an average and worst-case performance of O(n log n). If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n.