Complexity of Sorting Algorithms
Download the Cover Sheet for this lab as an Adobe PDF. This can be used to record your answers to the questions in the lab.
In previous exercises you have examined the efficiency of searches and sorts by looking at measures such as swaps and comparisons required in the algorithms. In Chapter 17, Big-O is described as a way to measure complexity of algorithms. In this lab assignment, you will reexamine some of the sorts you know and two you do not know using Big-O notation.
Go to each of the pages listed below and follow the directions.
Merge sort seems to come out on top in all of the experiments. If this is true, why would we ever use another sort? Can you think of another measure that we are not taking into account that might make Merge Sort less attractive?
After examining the various sorting algorithms with random data and ordered data, which sorts would be appropriate under each of the following circumstances?