Mastering Algorithms with Perl

Chapter 4. Sorting

The Librarian had seen many weird things in histime,butthathadtobethe57thstrangest. [footnote:hehadatidymind]

—Terry Pratchett, Moving Pictures

Sorting—the act of comparing and rearranging a collection of items—is one of the most important tasks computers perform. Sorting crops up everywhere; whenever you have a collection of items that need to be processed in a particular order, sorting helps you do it quickly.

In this chapter, we will explain what sorting is, how to do it efficiently using Perl’s own sort function, what comparing actually means, and how you can code your own sort algorithms with Perl.

An Introduction to Sorting

Sorting seems so simple. Novices don’t see why it should be difficult, and experts know that there are canned solutions that work very well. Nevertheless, there are tips that will speed up your sorts, and traps that will slow them down. We’ll explore them in this section. But first, the basics.

As in the two previous chapters, we’ll use addresses for our demonstrations. Addresses are an ideal choice, familiar to everyone while complex enough to demonstrate the most sophisticated attributes of data structures and algorithms.

On to sorting terminology. The items to be sorted are called records; the parts of those items used to determine the order are called keys or sometimes fields. The difference is subtle. Sometimes the keys are the records themselves, but sometimes they are just pieces of the records. Sometimes there is more than one ...