Wanted: tricky algorithm

[Tom Stockfisch]

In article <1317 at nusdhub.UUCP> rwhite at nusdhub.UUCP (Robert C. White Jr.) writes:
>in article <749 at acorn.co.uk>, enevill at acorn.co.uk (Edward Nevill) says:
>> Does anyone have, or can anyone think of an algorithm to
>> do the above
  [basically, sort a bunch of strings w/o allocating any more
   memory, given that you have an array of pointers to the strings]
>>without using an auxiliary array and with a
>> fairly decent running order (ie < N*N).
 
>The clasic "heap sort" is an in-place sort useful for such things,
>though it wouoldn't be that useful here becuse you have an index into the
>memory in the form of your array of pointers....

You've got a bunch of STRINGS, i.e., ascii data.
There in a block of memory but spread all over the place.
You want them sorted and compacted.
You don't want to allocate any more memory.
You don't want to spend a ridiculous amount of time.

The solution:

Sort the pointers in place using qsort().
Write the strings out in order to a temporary file.
Read the temporary file back in starting at the base of your memory
unlink() the temporary.
-- 

|| Tom Stockfisch, UCSD Chemistry	tps at chem.ucsd.edu