Which sort algorithm:
- Works in multiple passes.
- Performs less and less of the total work at each subsequent pass.
- 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.