Elementary Sorting Algorithms

There is a suprisingly diverse collection of algorithms that have been
developed to solve the apparently simple problem of "Sorting".

The general sorting problem is simple enough to describe: Given an
initially unordered array of N records, with one field distinguished as the
key, rearrange the records so they are sorted into increasing (or
decreasing) order, according to each record's key.

Sorting algorithms are used in all kinds of applications and are necessary,
for instance, if we plan to use efficient searching algorithms like Binary
Search or Interpolation Search, since these require their data to be
sorted.

Sorting algorithms are often subdivided into "elementary" algorithms that
are simple to implement compared to more complex algorithms that, while
more efficient, are also more difficult to understand, implement, and
debug.

It is not always true that the more complex algorithms are the preferred
ones. Elementary algorithms are generally more appropriate in the following
situations:

   * less than 100 values to be sorted
   * the values will be sorted just once
   * special cases such as:
        o the input data are "almost sorted"
        o there are many equal keys

In general, elementary sorting methods require O(N2) steps for N random key
values. The more complex methods can often sort the same data in just O(N
log N) steps. Although it is rather difficult to prove, it can be shown
that roughly N log N comparisons are required, in the general case.

Internal vs. External Sorting

Normally, when considering a sorting problem, we will assume that the
number of records to be sorted is small enough that we can fit the entire
data set in the computer's memory (RAM) all at once. When this is true, we
can make use of an internal sorting algorithm, which assumes that any key
or record can be accessed or moved at any time. That is, we have "random
access" to the data.

Sometimes, when sorting an extremely large data set such as Canada's Census
Data, there are simply too many records for them to all fit in memory at
once. In this case, we have to resort to external sorting algorithms that
don't assume we have random access to the data. Instead, these algorithms
assume the data is stored on magnetic tapes or disks and only portions of
the data will fit in memory. These algorithms use "sequential access" to
the data and proceed by reading in, processing, and writing out blocks of
records at a time. These partially sorted blocks need to be combined or
merged in some manner to eventually sort the entire list.

Stability

When a sorting algorithm is applied to a set of records, some of which
share the same key, there are several different orderings that are all
correctly sorted. If the ordering of records with identical keys is always
the same as in the original input, then we say that the sorting algorithm
used is "stable".

This property can be useful. For instance, consider sorting a list of
student records alphabetically by name, and then sorting the list again,
but this time by letter grade in a particular course. If the sorting
algorithm is stable, then all the students who got "A" will be listed
alphabetically.

Stability is a difficult property to achieve if we also want our sorting
algorithm to be efficient.

Indirect Sorting

One final issue to keep in mind when implementing a sorting algorithm is
the size of the records themselves. Many sorting algorithms move and
interchange records in memory several times before they are moved into
their final sorted position. For large records, this can add up to lots of
execution time spent simply copying data.

A popular solution to this problem is called "indirect sorting". The idea
is to sort the indices of the records, rather than the records themselves.
---------------------------------------------------------------------------