TAOCP #37 - Binary Merge

Caution Short Merge Ahead!

We're looking at optimum sorting. After analyzing what it means to minimize comparisons for sorting, Knuth turns to the related question of how to most efficiently merge two sorted sets in 5.3.2 Minimum-Comparison Merging. This is an optional starred section so expect a bit more math than usual.

We go over couple theorems on the minimum number of comparisons needed for merging from Graham/Karp, Hwang/Lim and Stockmeyer/Yao

We learn the proof technique of an adversary to establish these results

The constrained adversaries approach leads to Algorithm H (Binary merge) also from Hwang and Lim that takes its name from an application of binary search

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.2 Minimum-Comparison Merging (197--204)
  --- What is the best way to merge two ordered sets? (197)
  --- Theorem M (198)
  --- Constructing lower bounds, constrained adversaries (198--199)
  --- An adversary for merging, Strategy A (199)
  --- All strategies (199)
  --- Constraints on the strategies (200)
  --- Lower bounds on merging from the adversary, Table 1 (200--202)
  --- Theorem K (202)
  --- Upper bounds on merging (202--203)
  --- Algorithm H (Binary merging), Table 2 (203)
  --- Analysis of Algorithm H (204)

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

• Exercises
  --- Volume 3 (205--207)
• 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.