Rough sort first, fine sort later — and sorting for free
Shell sort fixes insertion sort's slow long-distance moves by comparing far-apart elements first. Tree sort barely needs new code at all — it is Unit II's BST and inorder traversal, renamed.
After this lesson
You should be able to
- Sort a small array by hand using shell sort with a given gap sequence.
- Explain why comparing distant elements first reduces total shifting.
- Implement tree sort using Unit II's BST insertion and inorder traversal.
Insertion sort's weakness: a small value stuck at the far end
CS105ES's insertion sort shifts one element at a time. If the smallest value in the whole array happens to sit at the very end, insertion sort must shift it past every other element, one slow step at a time, before it reaches its correct place near the front — like moving a suitcase across a room one inch at a time instead of picking it up and carrying it.
Shell sort: pack the big items first, then fine-tune
When you pack a suitcase well, you place the big items first, roughly positioned, then fill in the small gaps between them. Shell sort applies this idea to sorting: instead of comparing neighbors, it first compares elements a large gap apart, moving each one a long distance in one step. It repeats with a shrinking gap each round, ending with a gap of 1 — a plain insertion sort, but now run on data that is already roughly in order, so it finishes fast.
The far-apart comparisons in early rounds move badly-placed values most of the way home in a single step, which is exactly what plain insertion sort could never do — it only ever compares and shifts by one neighbor at a time.
Array: [9, 1, 8, 2, 7, 3, 6, 4, 5] gap sequence: 4, 2, 1
Gap 4: compare/insert (9,7), (1,3), (8,6), (2,4)
-> [7, 1, 6, 2, 9, 3, 8, 4, 5]
Gap 2: compare/insert within each even/odd sub-list
-> [6, 1, 7, 2, 8, 3, 9, 4, 5]
Gap 1: plain insertion sort finishes the job
-> [1, 2, 3, 4, 5, 6, 7, 8, 9]Tree sort: BST insert, then walk it in order
This is barely a new algorithm. Insert every value into a BST using Unit II Lesson 5's insertion, one at a time, then read them back out with Unit II Lesson 3's inorder traversal — left, then me, then right — which visits every value in sorted order by the BST property itself.
Its cost is exactly the sum of what you already know: n insertions, each costing the tree's height, plus one full traversal costing n. On a balanced tree that totals roughly n log n; on a degenerate tree — Unit II Lesson 5's sorted-input warning, still true here — it degrades to the cost of Unit I's plain linear structure.
Try it yourself
Sort [5, 2, 8, 1, 9, 3] using tree sort: draw the BST that results from inserting in this order, then write the inorder traversal.
Need a hint?
This is exactly Unit II Lesson 5's insertion algorithm, applied one value at a time, in the order given.
Check the worked solution
Inserting 5, 2, 8, 1, 9, 3 in order gives root 5, left subtree 2(1, 3), right subtree 8(_, 9). The inorder traversal visits 1, 2, 3, 5, 8, 9 — sorted, exactly as Unit II Lesson 3 promised it would for any BST, this one included.
Quick check
What is tree sort, in terms of algorithms from earlier in this course?
Why this lesson exists
Syllabus mapping
Shell Sort · Tree Sort
Maps to course outcomes CO1, CO2, CO3.