Performance and Test, Fall 2007: Episode 4.2

Lecture Friday, September 21, 10-12pm, room 3A14

Subject : Performance Characteristics of Sorting

Text : 6.6, 6.10, 7.1, 7.2, 7.3, 7.4, 10.0, 10.1, 10.2, 10.3, 10.6. This is an abridged list. See the explanation below [this abridged reading is approx 45 pages, 5 hours]

Downloads: Lecture notes. A table summarizing sorting algorithms was distributed as a hardocopy (search for left overs in the course pigeon hole).

Comments: In this lecture we will try to do the impossible: discuss all interesting sorting methods within two hours. I will not refer to all the details in the lecture. Contrary I will try to extract the information that is most essential from the user perspective. The lecture should give you a good guide to sorting techniques.

The broad coverage of the lecture implies that the reading list spans a huge material. You may find it particularly daunting if you have not studied sorting before. In any case remember that gory details of the sorting algorithms are not the most important for us in this lecture. What you should focus on is the preformance characteristics of each of the algorithms and the essential concepts related to sorting algorithms. So the most important sections are 6.6, 7.2, 7.3, 8.6, 10.6.

You should focus on general concepts and properties like stability, in-place, worst-case running time, average running time, space complexity, external sorting, sequential memory access, random memory access, linear sorting, sensitivity to input sequence, etc.

You should read entire chapters 6—10 during the semester (not necessarily before this lecture). Students without algorithmic background should use this opportunity to learn the basic computer science vocabulary and idioms. Sorting is really a fundamental piece of knowledge in this field that exempliefies techniques going way beyond sorting. Students with prior algorithmic training and with programming experience will likely find Sedgwick's presentation non-standard, discussing a lot of practical issues normally ignored in algorithms text. In particular chapters 7 and 8 are two very nice studies of improving the implementation, with a lot of good programming insight.