Analysis of merge sort
mergefunction runs in time when merging elements, how do we get to showing that
mergeSortruns in time? We start by thinking about the three parts of divide-and-conquer and how to account for their running times. We assume that we're sorting a total of elements in the entire array.
- The divide step takes constant time, regardless of the subarray size. After all, the divide step just computes the midpoint of the indices and . Recall that in big-Θ notation, we indicate constant time by .
- The conquer step, where we recursively sort two subarrays of approximately elements each, takes some amount of time, but we'll account for that time when we consider the subproblems.
- The combine step merges a total of elements, taking time.
mergeSorton an -element subarray as being the sum of twice the running time of
mergeSorton an -element subarray (for the conquer step) plus (for the divide and combine steps—really for just the merging).
mergeSorton an -element subarray (because we have to halve ) plus to merge. We have two subproblems of size , and each takes time to merge, and so the total time we spend merging for subproblems of size is .
mergeSortis the sum of the merging times for all the levels. If there are levels in the tree, then the total merging time is . So what is ? We start with subproblems of size and repeatedly halve until we get down to subproblems of size 1. We saw this characteristic when we analyzed binary search, and the answer is . For example, if , then , and sure enough, the tree has four levels: . The total time for
mergeSort, then, is . When we use big-Θ notation to describe this running time, we can discard the low-order term () and the constant coefficient (), giving us a running time of , as promised.
lowHalfand the other half in
highHalf. Because it copies more than a constant number of elements at some time, we say that merge sort does not work in place. By contrast, both selection sort and insertion sort do work in place, since they never make a copy of more than a constant number of array elements at any one time. Computer scientists like to consider whether an algorithm works in place, because there are some systems where space is at a premium, and thus in-place algorithms are preferred.