The Right Way To Teach Sorting

June 08, 2011

Last week, I said that C++ textbooks often make what I consider to be four mistakes:

• They teach readers how to write their own sorting algorithms before using the standard library.
• The first sort algorithm they teach has quadratic performance.
• They never teach how to write a sort algorithm that performs better; and
• They never get around to explaining what a stable sort is or why it is useful.

I also said that I had what I thought was a better way to do it. This article describes that better way.

Programs that sort often have to deal with three separate, but interrelated, problems:

• Sorting
• Merging
• Comparison

I am mentioning comparison as a separate problem because students so often get it wrong. For example, I've lost count of how many times I've seen code like this:

```    struct Point { int x, y; };

bool compare(const Point& p, const Point& q)
{
if (p.x < q.x && p.y < q.y)
return true;
else
return false;
}
```

Of course, the compare function could have used one line in place of four:

```          return p.x < q.x && p.y < q.y;
```

but either way, the code is wrong — at least if the intent is to use compare for sorting.

In order to avoid this common mistake, I think that it is important to be sure that students understand what comparison means before they learn how to sort. In order to do so, I think that it is a good idea to begin with merging, which is an easier problem than sorting.

Not only that, but once you know how to merge, you know how to sort, because of the following algorithm:

1. Is your sequence of length 0 or 1? If so, you're done.
2. Divide the sequence approximately in half, yielding two subsequences with lengths that differ by no more than 1.
3. Sort each subsequence.
4. Merge the two sorted subsequences.

You might think that (3) is problematic: How can we sort a sequence without first knowing how to sort it? However, (1) shows us how to sort very short sequences, and each time we reach (3), we make a recursive call that deals with ever-shorter sequences until eventually we reach (1).

This algorithm is, of course, a recursive implementation of Mergesort. If it is implemented correctly, it is stable, and it runs in O(n log n) time. Of course, it consumes extra space; but O(n) extra space is usually much better than O(n2) time.

Therefore, I think that a reasonable way to teach students about sorting is:

1. Use the standard sort algorithm.
2. Show students how to write a comparison function, explaining about order relations along the way.
3. Show how to merge sorted sequences, first using the standard merge algorithm and then writing it explicitly.
4. Show how to write Mergesort by combining merging and recursion.

It is probably true that these four steps together take more teaching time than simply instructing students on how to write a bubble sort or an insertion sort. However, not only do the students learn about sorting, but they also learn about merging, comparison, and recursion. Moreover, they do so without picking up any bad habits along the way.

More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>