previous | start | next

## Analyzing the Merge Sort Algorithm

- How does O(n2) compare to O(n log n)?
- Recall that it takes 1002 = 10,000 times longer to sort 1,000,000 records than it takes to sort 10,000 record with the O(n2) 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

previous | start | next