Sorting and Searching

Analyzing the Merge Sort Algorithm

How does O(n²) compare to O(n log n)?
Recall that it takes 100² = 10,000 times longer to sort 1,000,000 records than it takes to sort 10,000 record with the O(n²) algorithm.
With the O(n log n) algorithm, the ratio is
If it takes 4 seconds to sort 10,000 records for both sorts (merge sort is really faster, of course) then
- it will take 10 minutes to merge sort 1,000,000 records
- it will take 11 hours to selection sort 1,000,000 records