bugfix: indeterministic file choice from multiple sources

[Dirk Pape]

Hello Paul,

--Am Mittwoch, 25. August 2004 16:59 Uhr +0200 schrieb Paul Slootman 
<paul at debian.org>:

> In the meantime I'm curious about the relative memory usage of qsort
> vs. mergesort.  I'd hate rsync's memory usage to go up again.

as far as I am informed (I am not a profi in complexity)

mergesort has better worst case time complexity and equal average time 
complexity than/as quicksort

space complexity is also the same (both are linear :-) but mergesort uses 
double space of quicksort in worst case.

On Linux with gnulibc libc chooses mergesort instead of qsort for you if 
"space is enough" (I hate *this* hidden "optimisation"!). So if you are 
experiencing too high memory consumption with long file lists on Linux you 
might actual see mergesort at work.

Dirk.