Re: Synchronization routine

On Mon, 31 Oct 2005 13:36:17 +0000 (UTC), Willem <willem@xxxxxxxx>
wrote:
[snip much that is good]

>Mergesort would still descend into smaller and smaller partitions.
>It doesn't magically know that the data happens to be sorted.
>In fact, the running time of mergesort is always the same(*).


It isn't quite true that the running time of mergesort is always the
same. When merging two runs of length n the number of comparisons
required may be anything between n and 2n-1.


Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
I started out in life with nothing.
I still have most of it left.
.