People need to sort things all the time. Investment advisors sort portfolios by the profit each holding generates. Doctors sort lists of transplant patients.
Mail programs sort messages.
More generally, sorting lists of values by some criteria is a task that many programs need to perform. Here we study how to sort a list of numbers because it is important for many programming tasks, but also because it provides a good case study concerning the design of auxiliary programs. A sorting function consumes a list and produces one. Indeed, the two lists contains the same numbers, though the output list contains them in a different order. Next we must translate the data definition into a function template.