# The Right Way To Teach Sorting

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:

- Is your sequence of length 0 or 1? If so, you're done.
- Divide the sequence approximately in half, yielding two subsequences with lengths that differ by no more than 1.
- Sort each subsequence.
- 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(*n*2) time.

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

- Use the standard
**sort**algorithm. - Show students how to write a comparison function, explaining about order relations along the way.
- Show how to merge sorted sequences, first using the standard
**merge**algorithm and then writing it explicitly. - 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.