Wanted: tricky algorithm

[Felix Lee]

In article <749 at acorn.co.uk>,
   enevill at acorn.co.uk (Edward Nevill) wants
to reorder strings in a blob of memory according to a sorted array of
pointers to the strings, using constant memory.

The obvious algorithm (obvious to me, at least) runs in something like
O(n*n + n*m) time, where n is the number of strings and m is the size
of the blob of memory.

Given
  a[0 .. m-1] the blob of memory
  s[0 .. n-1] indexes into a[], referring to the strings
  l[0 .. n-1] the lengths of the strings

  // invariant: a[0 .. p-1] contains the strings s[0 .. i-1]
  //   in the right order
  p := 0
  for i in 0 .. n-1 do
    swap a[p .. s[i]-1], a[s[i] .. s[i]+l[i]]

    for j in i+1 .. n-1 do      // adjust the string pointers
      if s[j] < s[i] then s[j] := s[j] + l[i]

    s[i] := p; p := p + l[i]

Note that the "swap" exchanges unequal-sized segments.  This can be
done in place.

Less obvious algorithms are . . . less obvious.  I can't seem to come
up with any.  The amount of character swapping, O(n*m), feels like it
could be reduced by something suitably clever.  Maybe if the memory
constraint were relaxed a bit. . . .
--
Felix Lee	flee at shire.cs.psu.edu	*!psuvax1!shire!flee