Sorting: An Overview

Computers and Sorting

A computer program may (as in the case of the binary search algorithm) find it convenient, or necessary, to have the data it is working with in sorted order. Or not, as in the case of "hashing" algorithms. Humans, on the other hand, almost always prefer to have their data in some kind of sorted order. For this reason alone, computers spend a great deal of their time sorting values of one kind or another.

Internal Sorting and External Sorting

By internal sorting we mean that all the data being sorted is held in the computer's memory while it is being sorted.

By external sorting we mean that some or all of the data being sorted is held in the external storage while it is being sorted.

Meaning of sorted

What, exactly, does it mean to say that a sequence of data values is sorted?

First of all, the data values must have keys (or, in simple cases such as numbers, characters or strings, the data values can themselves be keys). Keys are simply quantities that can be ordered. Then, if k_i is the key of the i^th data value in a sequence of data values, we say that the sequence is sorted, provided that

k_i precedes k_j whenever i < j

Don't forget, however, that this in turn depends on the precise meaning of precedes, which will often be <=, since we are often sorting in ascending order but can just as easily be >= if we are sorting in descending order, and for that matter it can be any other suitable relationship which determines when one value precedes another.

Basic Assumptions for Sorting Algorithms

As is almost always the case (and is always a good idea), sorting algorithm pseudocode should (ideally) be programming-language independent. Also, the pseudocode for a given sorting algorithm need not specify whether ascending or descending order is taking place. That depends on the "level" of the pseudocode, and the choice may be left to the implementor.

However, by default the implementation of any sorting algorithm in any sample program on this site, as well as the sorting algorithms students may be required to implement or to answer questions about on a test or exam, will do the following:

• It will sort values into ascending order, unless there is an explicit indication to the contrary.
• It will make any required "passes" over the data (or any portions of it) from left to right (from low index to high index in the vector containing the data), unless there is an explicit indication to the contrary.

Keep in mind, though, that when we are looking at data and speaking of it "being in ascending order" or "being in descending order", we are always visually scanning the data from left to right.

In any case, a programmer must be able to recognize whether in fact a given algorithm does sort into ascending or descending order, and must be able to modify any given algorithm to sort "in the opposite direction". A programmer must also be able to deal with sorting algorithms in other than "garden variety" situations (for example, sorting a row or column of a two dimensional array, as well as sorting just a one-dimensional array or vector).