Lecture 22
Today we addressed external memory issues
when sorting. MergeSort was discussed in it's usual form as well as versions
that
- start with block of sorted
data.
- use k-way merges.
These modifications are
motivated by the need to reduce the number of disc accesses.
This more or less brings us to
the end of chapter 21 of the text. On Wednesday I will fill in a few missing
pieces regarding B-trees and external sorting with tapes. All of chapter 21 is
required reading. I have updated the "Readings" entry to reflect this.
Also note that Section 19.8 is
back on the reading list.
Posted: Mon - March 7, 2005 at 03:33 PM