Keys

This formalization of sorting basically requires that we specify sorting algorithms in terms of comparisons and duplications of keys.

To deal with large records, we can sort the keys along with pointers to the entire record (so we don't have to keep moving the whole object around).

In some cases, the keys themselves are very large. In this case, both comparison and duplication could take substantial amounts of time. More sophisticated algorithms are needed in this case (especially if we assume that the data doesn't fit into main memory!).


next up previous
Next: Sorts of Sorts Up: SORTING Previous: Beyond Adjacency