Which sort algorithm:

  1. Works in multiple passes.
  2. Performs less and less of the total work at each subsequent pass.
  3. When visualized, makes it clear that the decreasing amount of work at each stage is the result of "reaping the benefits" of the work done in previous stages.

The Long version

My nephew is having trouble with math at school and his teacher's methods don't seem to be doing him much good either, so I've begun to tutor him here and there and it's become clear that he has some gaps in his understanding which are hindering his progress. However, he resisting review of things he feels he is already familiar with because this feels like a waste of time to him, after all he "knows that already!". He's a bright kid but like so many children these days (and possibly since the dawn of mankind) he seems to want to rush ahead as quickly as possible, which hurts him in the long run.

There's ample pedagogical evidence that the mastery of a subject before progressing yields better results in the long run, but this can obviously feel like progress is much slower when you're just getting started. I've certainly felt that way and had to discipline myself to believe that deep understanding will beat mechanical routine in the long run (proficiency is important as well, of course).

So partly in an effort to make this case to him convincingly and perhaps mostly because I have a natural tendency to think about such things in algorithmic terms, I'm asking: which (if any) sorting algorithm(s) serve as a good illustration of this principle, that slow progress (more work?) in the initial stages makes subsequent steps easier (less work).

Quicksort's recursive nature isn't a good fit, and neither is merge sort. Insertion sort takes longer at each step (on average, about $k/2$ comparisons at stage $k+1$, I think) while bubble sort only does one comparison less at each pass.

I'm not concerned about $O(n^2)$ vs. $O(n\log n)$, sorting is an imperfect analogy for learning anyway. I'm just looking for a process I can visualize for him, that will set him thinking and that, hopefully, will give him a model to grab onto for use as a mental model for the process of learning (math), a model that places emphasis (and justifies the hard work involved in) on understanding of concepts instead of the memorization of procedures, even when it seems this gets you to the final answer more slowly.

The answer doesn't have to be a sorting algorithm actually, it just seems like the most natural place to look for such an example.

* Bonus points for providing an animation.

  • $\begingroup$ For another graphical approach to sorting algorithms, visit sortvis.org - be sure to include cyclesort and shellsort. $\endgroup$ – greybeard Dec 28 '15 at 6:23
  • $\begingroup$ Insertion sort takes [on average] about k/2 comparisons at stage k+1, I think - using linear search for the point of insertion for "uniform random keys". Others claim the serving graces of insertion sort being the opportunity to binary search for that ($ld(k)$ comparisons - non-decreasing) and use bulk move. Everyone's mileage will vary. $\endgroup$ – greybeard Dec 28 '15 at 10:22
  • $\begingroup$ I don't think any (classical) algorithm will fit the bill here, because for an algorithm going back and revisiting already solved subproblems are a waste of time. The point is that (unlike an algorithm) humans have to iterate the same thing in order to achieve mastery. $\endgroup$ – Raphael Dec 28 '15 at 11:17

Bubble Sort

After each iteration the amount of elements to be compared reduces by one. Will serve a good analogy to working in passes and the amount of work decreases on each pass.

If there is no constraint for analogy the analogy to be from sorting only, then you can use memoization .

  • $\begingroup$ The question explicitly says that bubblesort doesn't fit the bill, though I'm not convinced about the reasoning given there (as you say, it does -- slightly -- less work on each pass, not more as the question claims). $\endgroup$ – David Richerby Dec 27 '15 at 22:28
  • 1
    $\begingroup$ @DavidRicherby I totally agree. In the question it said that the bubble sort takes more time but in reality it is one "step" less in each iteration. $\endgroup$ – May Rest in Peace Dec 27 '15 at 22:30
  • $\begingroup$ You're both right, I'll amend the question. Still, bubble sort doesn't do significantly less work at each step, so doesn't capture the idea I'm after. $\endgroup$ – Jake Baron Dec 28 '15 at 1:55

Perhaps insertion sort fits the bill (build up a stretch of sorted elements, insert the next one at it's proper position among them). A totally non-obvious technique doing as requested is Shell sort. Wikipedia's page on sorting might help finding something appropriate (or at least show that there are many different ways to solve that particular problem, which in itself is sobering to people looking for the solution).

  • $\begingroup$ With insertion sort, the complexity of the insertion never decreases, but increases every once in a while. $\endgroup$ – greybeard Dec 28 '15 at 0:07
  • $\begingroup$ @greybeard the insertion job gets longer, but the total job remaining decreases. $\endgroup$ – vonbrand Dec 28 '15 at 0:13
  • $\begingroup$ The second item from the damagement summary reads Performs less and less of the total work at each subsequent pass. While I'm uncomfortable with pass (see comment on question), the number of elements expected to need a shift increases linearly, dominating the increase in the number of comparisons. $\endgroup$ – greybeard Dec 28 '15 at 1:02

I believe you have discounted quicksort too easily, because the usual way quicksort gets explained is through recursion.

Instead, explain quicksort as repeatedly 'splitting up' the array, until all the splits have size 1. And instead of doing usual recursion, keep a priority queue of the biggest subarray that we can split, breaking ties by splitting up the leftmost subarray. This may sound a lot more complicated, but this priority queue is not kept at all! Spotting the biggest subarray is instantly visually recognizable for a human.

Here is a visualization I made of quicksort running in this fashion:

quicksort visualization

Sadly it would be too much work for one answer to visualize the splits.

  • $\begingroup$ Interesting approach to assessing quicksorts efficacy - instantly made me want to compare median of (one, ) three and five and quickselect. $\endgroup$ – greybeard Dec 28 '15 at 6:21
  • $\begingroup$ "Here is a visualization I made of" -- did you make it? It sure looks familiar. Please attribute any sources you use, otherwise you are violating others' rights. $\endgroup$ – Raphael Dec 28 '15 at 11:15
  • $\begingroup$ @Raphael I used the sound of sorting software, edited it to implement the modified quicksort mentioned above, and recorded a gif of the program running. I probably should have mentioned the software from the beginning, I merely meant that I'm the creator of the gif, not the software seen in the gif. $\endgroup$ – orlp Dec 28 '15 at 12:42
  • $\begingroup$ Fair enough, thank you for explaining. $\endgroup$ – Raphael Dec 28 '15 at 12:44

Maybe try bucket sort with large input to show that buckets are collecting similar numbers, and then it is trivial to take them. When we take introsort as example, it is more beneficial to show different steps.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.