8.17. Merge Sort Compared¶
We have established that the Merge Sort algorithm requires \(O(n·log_2(n))\) work to sort a list of size n. How does that compare to Insertion and Selection sort that are \(O(n^2)\)?
Below is a graph of the growth of \(n^2\) and \(n·log_2(n)\):
Obviously, \(n^2\) grows much faster than \(n·log_2(n)\). 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!
Problem size |
10 |
100 |
500 |
1,000 |
10,000 |
100,000 |
|---|---|---|---|---|---|---|
\(n \cdot log_2(n)\) |
33 |
664 |
4,483 |
9,966 |
132,877 |
1,660,964 |
\(n^2\) |
100 |
10,000 |
250,000 |
1,000,000 |
100,000,000 |
10,000,000,000 |
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 more 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 actually 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·log_2(n))\), 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?
