External sort compo?

[stylin]

Assume we had a file where the data portiion was already sorted by name. Now we want to sort the file by zipcode. Using a stable sort, we just need to sort on the zipcode key, and the names will still be in sequence within each zipcode. For an unstable sort, we would have to sort on 2 keys, the zipcode as major and the name as minor --- more time.

I think you have that backwards.

In an unstable sort, if two records' zip codes compare equal, it's not guaranteed that the record on the lhs will stay on the lhs: the order of the two equal records may be switched, it just depends on the sorting implementation. Unstable sorts are faster because they don't have to worry about relative position; they can just put a record at the most convenient (efficient) spot in the sorted list.

Stable sorts do have to keep the relative position of two equal records, thus are slower, since any arbitrary position for a record won't do.

You can add more sort criterion - for example by name - but all you're changing is the definition for equality - you still have to decide what to do with two (fully) equal records (whether that equality is based on zip code, name and/or whatever). The distinction is subtle, but IMO, important.

BTW, when Antoni says "REGISTER" he is translating from Spanish, and he really means "RECORD".

Yeah, I was confused for a minute there.