The Sorting Problem

• We will now undertake a more formal study of algorithms for the sorting problem. • This problem is fundamental to the study of algorithms. • Most often, the items to be sorted are individual records, usually consisting of a key and related satellite data. • Recall our previous definition (slightly generalized here). Input: A sequence of n records a1, a2,..., an. Output: A reordering a′1, a 2,..., a n of the input sequence such that a′1 ≤ a′2 ≤ · · · ≤ a′n. • Note that the records can be anything for which a “≤ ” operator can be defined (usually by comparing the specified key). • We may be interested in sorting the same list in more that one way. • What are some contexts in which sorting is important? 2 IE170 Lecture 7