TAOCP #36 - Merge Insertion Sort

It's The Best Sort, Don - The Best!

Knuth - "Of course there is no best possible way to sort"

What Knuth offers instead are three sections on minimizing the number of comparisons while sorting, merging or selecting

We look at the first section under 5.3 Optimum Sorting in this meetup - 5.3.1 Minimum-Comparison Sorting

We introduce comparison trees to establish a theoretical framework for analyzing comparison-based sorting techniques

Then we consider two problems - finding comparison trees that minimize the maximum number of comparisons made - similarly those that minimize the average number of comparisons

More concretely we learn merge insertion sort that came about as a generalization of a solution to the question - "What is the best way to sort five elements? Can five elements be sorted using only seven comparisons?"

We'll do some exercises

This event will be recorded and posted to YouTube as a public video at https://www.youtube.com/channel/UCHOHy9Rjl3MlEfZ2HI0AD3g

Keep the conversation going!

Facebook: https://www.facebook.com/groups/678335496099220
IRC ##taocp: https://webchat.freenode.net/##taocp

Agenda:

2:00 - 2:10 Meet and greet
2:10 - 3:00 Read and discuss couple pages at a time from Chapter 5, Sorting (along with MMIX Supplement)

• 5.3. Optimum Sorting/5.3.1 Minimum-Comparison Sorting (pp.180-187, 192-193)
  --- Binary comparison tree (pp.180-182)
  --- The best worst case (pp.182-184)
  --- Merge insertion (pp.184-185)
  --- Analysis of merge insertion sort (pp.185-187)
  --- The average number of comparisons (pp.192-193)

3:00 - 3:10 Break
3:10 - 4:00

• Exercises
  --- Volume 3 (pp.193-197)
  --- MMIX Supplement (p.94)
• Shoot the breeze

Note on MMIX and MIX:

The MMIX is a hypothetical computer designed by Knuth. It is a successor to MIX which is still referred to in all printings of Vols. 1-3 of TAOCP. MMIX is significantly different from MIX. In order to use MMIX instead of MIX now means having to supplement TAOCP with two primary sources.

The first supplement is Fascicle 1, MMIX, a booklet written by Knuth describing the computer and its assembly programming language. It replaces Sections 1.3 and 1.4 of Chapter 1, Basic Concepts. The section numbers in the fascicle have a prime (') suffix to distinguish them from the originals, e.g. fascicle section 1.3.1' replaces TAOCP section 1.3.1.

The second supplement is The MMIX Supplement by Martin Ruckert that has MMIX versions of all programs and content in TAOCP that currently refer to the older MIX computer. It uses the same section numbers as in TAOCP with page references and text snippets from TAOCP to help sync the MMIX version of the content with its location in TAOCP.