bugfix: indeterministic file choice from multiple sources

Dirk Pape pape at inf.fu-berlin.de
Thu Aug 26 07:18:52 GMT 2004

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.


More information about the rsync mailing list