... 2.102.1
That's Figure 2.10 in [2], page 16. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... Figure 3.23.1
It means Figure 3.2 in [2], page 20. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... tail-recursive3.2
Actually, this new merge function is a trivial wrapper around its helper function, which is tail-recursive. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... done.4.1
When K = N, this final column is roughly $\frac{1}{2}$ because insertion sort on randomized lists, which is how I generated the data to sort, is close to $O(\frac{N^2}{2})$. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... true6.1
``True'' is any non-NIL value. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... all.6.2
For what it's worth, the same memoized test on clisp on Microsloth Winders showed even closer & more consistent performances. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... N)6.3
Log (log N)?! Am I sure about this? fixme: What is the predicted performance? 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.