bugfix: indeterministic file choice from multiple sources
pape at inf.fu-berlin.de
Thu Aug 26 07:18:52 GMT 2004
--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