Many of you headed down complicated paths when asked to implement sort following the template today. Most of you ran into one of two (related) problems:

- You started thinking about algorithms too early
- You weren't sure how to use the template

Templates defer questions about the logic/algorithm of a program until after its core structure is in place. If you know how to use the template, you get a lot of code written down that can then help you think out an algorithm. The design process becomes a lot more manageable.

Writing the template means writing the **whole** template, not
just the cond (because as soon as you had that much you started
thinking about the algorithm). The whole template for sort looked
like

;; sort : list-of-number -> list-of-number[sorted] ;; sort list of numbers into increasing order (define (sort alon) (cond [(empty? alon) ...] [(cons? alon) ... (first alon) ... (sort (rest alon))]))

If you gave any thought to the sort algorithm before you had this much on paper, you started thinking about the algorithm too early.

Filling in the empty case was easy -- that came from the examples.
What do you do in the cons case? Again, many of you started thinking
about the algorithm, instead of thinking about what the template
*gave you for free*. To use the template, ask yourself the
following questions:

- What does (first alon) give me? [Answer: a number]
- What does (sort (rest alon)) give me? [Answer: the rest of the list sorted -- read this right off the purpose statement!!]
- How do I combine a number and a sorted list of numbers into a
sorted list of numbers? [
**Here's the algorithm part!**]

Answering the third question leads you to an algorithm: stick (or insert) the number into its appropriate place in a list of numbers. How do you do that? That sounds like a straightforward program on list of numbers (it is, and one you should certainly be able to write). Modify the template with a helper function name for this new algorithm you need, then write the insert helper function to finish sort.

;; sort : list-of-number -> list-of-number[sorted] ;; sort list of numbers into increasing order (define (sort alon) (cond [(empty? alon) empty] [(cons? alon) (insert (first alon) (sort (rest alon)))]))

Learning to ask yourself the template questions above (what does each piece give me and how do I combine them--use the contract and purpose to help) will dramatically improve your skills at working with templates. Internalize these questions.

Doesn't this suggest that you can never write a different sorting algorithm besides insertion sort? Tune in next time ...