We have established that the merge sort algorithm requires \(O(n \cdot log_2(n))\) work to sort a list of size n. Because that is a linear value times a logarithmic value, that is known as log linear. How does log linear growth compare to insertion sort and selection sort, which grow at a quadratic rate (\(O(n^2)\))?
Obviously, \(n^2\) grows much faster than \(n \cdot log_2(n)\text{.}\) Looking at the table below, we can see that sorting 500 items with Insertion Sort (\(O(n^2)\)) would take somewhere around 250,000 units of work. Doing the same task with Merge Sort would only take around 4,483 units of work!
Look closely at the gap between \(n\) and \(O(n \cdot log_2(n))\) and then compare it to the gap between \(O(n \cdot log_2(n))\) and \(O(n^2)\text{.}\)
Using the Big-O classification of each algorithm like this gives us a rough estimate of the work. We are ignoring constant factors that may change the exact numbers (especially for low values of n). Merge Sort has a greater basic overhead than Insertion Sort (for example, we have to copy items to and from a second list) - if you are solving small problems it may take more time to run than Insertion Sort due to this. But we know that as n grows larger the basic pattern is going to hold - \(O(n^2)\) is going to grow faster than \(O(n \cdot log_2(n))\text{,}\) so Merge Sort will certainly be faster out for large values of n.
Below, you can use the Sort Timer to simulate running sorts of different sizes using the two algorithms. You can use the slider to change the size of the list being sorted. Try comparing the two algorithms at different sort sizes. Does Merge Sort always win? At what point does Insertion Sort start taking more than a half-second to run? At what point does Merges Sort start taking more than a half-second?
