Re: sorting in C

[Andrew Cohen]

Mattias E. reminds me (in a private email):
>Since Timsort may allocate temporary scratch space it is important to
>make sure it's freed if the comparison predicate throws. A specbind
>may be needed for the clean-up, but I haven't looked at your timsort
>code -- perhaps you have already solved that problem.

Dealing with the tmp space is my one remaining question. I note that
when sorting a list of length L, the current (vector) sorting routine
requires space for a tmp array of length L/2.  It uses SAFE_ALLOCA_LISP
(and SAFE_FREE) outside the sorting routine and passes a pointer to the
storage as an argument to =sort_vector_inplace=. This way memory
management is easy.

TIMSORT /also/ requires space for a tmp array of length L/2, but only in
the worst case (random lists). For partially sorted lists it can make do
with less. So it takes a dynamic approach: it allocates a small amount
of storage (enough for an array of length 256) which can handle all
short lists and longer partially sorted lists; and then allocates
additional storage on the fly as needed for other cases.

Right now my routine accepts a pointer to tmp space as an argument; if
this is null, it uses the dynamic allocation, and otherwise just uses
the pre-allocated storage.

Clearly the less memory required the better, and for mostly-sorted lists
the pre-allocated 256 is usually sufficient. This saves the space, and
any (minimal) time needed to allocate additional space.

But the early allocation of the maximum space required (as is done for
the current sorting routine) makes the memory management trivial (which
is good!) and avoids the (minmal) additional time for allocs for random
lists.

I'm inclined to just go with the current system: allocate the maximum
required before calling the routine, but welcome any advice or
expressions of preference for the dynamic allocation. 



-- 
Andrew Cohen