An improved merge-sort algorithm

[Wayne Davison]

Hi there.  When I added a merge-sort algorithm to rsync, I improved upon
the glibc version to reduce the amount of copying it does and to half
the needed memory.  I thought you might be interested in updating the
version in glibc, so I'm attaching a patch that applies to the CVS
version.

The algorithm is simple:

When dividing a buffer, b, into b1 and b2 halves and getting each half
sorted (recursing into this algorithm), we join the lists by first
comparing the starting item(s) in the b1 section to find one that is
larger than the first item in b2.  If none are found, no copying is
needed.  If one or more are found, the remaining b1 items are copied
into temporary-memory (making the maximum needed tmp memory the size of
b1), and then the remaining items are merged from tmp and b2 back into
the b buffer starting at the spot where the b1 items were copied away.
Any b2 items that are already in place at the end of the buffer are not
copied at all (which is the same as the current algorithm).

Compared to the old merge-sort algorithm, here is the amount of copying
needed for various situations:

 - If sections b1 and b2 are in sequence as a group, the new algorithm
   does no copying.  The old algorithm copied b1 to tmp and tmp back to
   b1, so this saves 2 useless b1-sized copies with no increase in
   comparisons.

 - If sections b1 and b2 are in the opposite order, the new algorithm
   copies b1 to tmp, and then copies b2 followed by tmp back to the b
   buffer.  The old copied b2 + b1 to tmp, and then copied them both
   back again, so the new code does 25% less copying in a worst-case-
   order situation.

 - In a case where 1/2 the leading and 1/2 the trailing data is already
   in the right spot, the new algorithm results in 50% less copying.

 - Etc.

Since the algorithm is a little more complex than the old one, I decided
to use a macro as a function template.  I also created a separate static
function for each of the separate copy-size cases instead of using a
switch inside a single function.  A small number of inline copy-one-item
functions makes the template easy for all the types.

I also moved the (n <= 1) exclusion at the start of the msort function
into the calling functions (one spot in qsort() and when recursing).
This saves 1-2 useless recursion calls when we reach 1-item lists.

This version has received light testing to ensure all the msort_TYPE()
functions work properly for a simple test case.

..wayne..
-------------- next part --------------
A non-text attachment was scrubbed...
Name: msort.patch
Type: text/x-diff
Size: 7899 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20071210/a2126fe0/attachment.bin>