CS 111: Introduction to Computer Science

Timing sorting algorithms

The sorter.py program is set up to allow you to collect running time data from a variety of sorting algorithms. To get the usage statement, just grab a copy of the program and run "python sorter.py".

In this lab exercise, you will use running time data to try to persuade your audience (that's me!) that various sorting algorithms have various behaviors. In particular, your goals for this lab are:

1. Convince me that Insertion Sort's running time is approximately proportional to N2, where N is the number of items being sorted.
2. Convince me that Merge Sort's running time is approximately proportional to N x log2(N).
3. Tell me what you can determine about Selection Sort's running time.
4. Tell me what you can determine about Python's built-in "sort" method's running time.

Hand in your arguments either via e-mail or on paper at the end of the lab period. We'll talk in class on Wednesday about what people came up with.

By the way, the base two logarithm behaves like this. Since 29 = 512, log2(512) = 9. That is, the logarithm equation is an equivalent way of writing an exponential equation. You can insert a formula into Excel like so: "=LOG(512, 2)" to see the same idea at work.