Some Standard Sorting Algorithms

The problem of putting a collection of values in order appears so frequently that it's one of the most commonly studied problems in computer science. As with many problems, it has many different potential solutions. In this document, we consider a few of the standard algorithms that computer scientists have developed over the years.

As you read through these algorithms, you might want to try running them by hand to see how (and whether) they work.

Selection Sort

Selection sort relies on your ability to easily identify the smallest value in the collection. To sort using selection sort, you repeatedly (1) identify the smallest value and (2) put it at the front of the values not yet identified. We can naturally phrase this algorithm recursively.

To sort a list of values using selection sort
  If the list is empty then
    You're done
  Otherwise
    Identify small, the smallest value in the list
    Remove small from the list
    Sort the modified list
    Shove small back on the front of the sorted list

Of course, for this algorithm to work, we need a way to find the smallest value in a list and to remove an element from a list. We'll consider finding the smallest value and leave removal as a thought problem.

It's fairly easy to find the smallest value in a list. Here are two techniques, one using repetition and one using recursion.

To find the smallest value in a list (version 1: repetition)
  Let guess be the first value in the list
  For each value, val, in the list
    If val < guess then
      Let guess be val
  guess is now the smallest value in the list

To find the smallest value in a list (version 2: recursion)
  If the list contains only one element then
    That element is the smallest value in the list
  Otherwise
    Let first be the first element in the list
    Let guess by the smallest value in the remainder of the list
    The smaller of guess and first is the smallest
      value in the list

Insertion Sort

Insertion sort works by building the sorted list from the bottom up. We repeatedly take the first element from the list to be sorted and put it in the correct place in the sorted list.

To sort a list, lst, using insertion sort
  Create an empty list sorted
  Insert each value in lst into the correct place in sorted

To insert each value in lst into the correct place in sorted
  For each value, val in lst
    Insert val into the correct place in sorted

Note that we might also want to phrase a key step in insertion sort recursively.

To insert each value in lst into the correct place in sorted
  If lst is empty then
    You're done
  Otherwise
    Insert the first element in lst into sorted
    Insert the remaining elements in lst into the new sorted

In either case, we rely on a helper procedure. This time, the goal of the procedure is to insert a value into a sorted list.

To insert one value, val, at the proper position 
in a sorted list, slist
  Possiblity One: slist is empty
    Make a list from val
  Possiblity Two: val is less than or equal to 
  the forst value in slst
    Add val to the front of slst
  Possibility Three: val is greater than the first value
  in slst
    Keep the first value in slst and insert val into
    the rest of slst

Merge Sort

Both selection sort and insertion sort build the sorted list one element at a time. As you get more experience in computer science, you'll quickly learn that there are sometimes better ways to break up your work. The divide-and-conquer technique suggests breaking your work in half (or other large parts). We can use that technique along with recursion to come up with a sorting algorithm called Merge Sort.

To sort a list using merge sort
  Split the list into two equal halves (or as equal as possible)
  Sort each half
  Merge the two halves together

Once again, we rely on some helper algorithms. We need a way to split the list in half and a way to merge two sorted lists into one sorted list. We'll leave splitting as an exercise to the reader. Merging is somewhat more interesting.

To merge two sorted lists, slst1 and slst2
  Possibility 1: slst1 is empty
    Just use slst2
  Possibility 2: slst2 is empty
    Just use slst1
  Possibility 3: The first element of slst1 is less than
  element of slst2
    Use the first element of slst1 as the first element
      of the merged list.
    Build the rest of the merged list by merging the rest of slst1
      with slst2.
  Possibility 4: The first element of slst1 is not less than
  the first element of slst2
    Use the first element of slst2 as the first element
      of the merged list.
    Build the rest of the merged list by merging the slst1
      with the rest of slst2.