Sorting Algorithms: Introduction
(Up to Basic Computer Science : Lists and Arrays)

Sorting has been analyzed by computer scientists for decades, and thus it is an ideal subject to begin with when studying computer science. Sorting is done with algorithms, which are a set of specific commands that are followed in a certain order to complete a task. A cooking recipe is an algorithm, but we usually reserve the word algorithm for mathematics or science related topics.

To study sorting, you must first be comfortable with iteration and recursion. These two terms designate the ways tasks are repeatedly performed. A jolly old programmer might give you this definition of recursion:

re-cur-sion (ri-'ker-zhen) n See recursion.

If you don't know what iteration and recursion are and how they are different, look up a book on a common programming language like C++ and it should tell you. Or, you can go to Cprogramming.com, which has tutorials on C++ with a section on recursion.

Note: in most of these algorithms, two elements of an array are often switched. So, to make the algorithms easier to read, we have written a function called swap() which takes two variables and exchanges the values in them. Here is the function code in C++:

inline int swap( int &x, int &y )
{
  int z = x;
  x = y;
  y = z;
}

Note as well that we are using C++. For all the example code in this site, we will be using C++, for it is a widely used and taught language that is efficient and suitable for our purposes.

The basic sorting algorithms are mostly iterative, and thus probably easier to understand.

The most simple algorithm, but not the most intuitive algorithm, is Bubble sort. This sort is still used a lot because it is easier and shorter to type than the other sorts.

The most intuitive algorithm is Selection Sort. Humans use this sort all the time when sorting objects. This algorithm is especially useful when sorting across a network.

Radix Sort (also known as Bin Sort) is a fairly fast sort that uses digits of numbers to sort arrays. Because of this, however, Radix Sort is fairly specialized, and makes it difficult to write general purpose code.

A very important sorting algorithm is Insertion Sort. This sort may not seem important, but it is used a surprising amount because it works well with almost sorted arrays.

One of the advanced sorting algorithms is the Heap Sort, which is based on the Heap Tree. You should read the two essays on Data Trees and Heap Trees before you attempt to read about this sort.