Re: [PATCH 1/3] add mergesort() for linked lists

From: Junio C Hamano <gitster@pobox.com>
Date: Apr 5, 2012, 19:17 UTC
Message-ID: <7vpqbm56pf.fsf@alter.siamese.dyndns.org>
In-Reply-To: <4F7780C3.2050408@lsrfire.ath.cx>

René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:

Show 56 quoted lines

> This adds a generic bottom-up mergesort implementation for singly linked
> lists.  It was inspired by Simon Tatham's webpage on the topic[1], but
> not so much by his implementation -- for no good reason, really, just a
> case of NIH.
>
> [1] http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
>
> Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
> +void *mergesort(void *list,
> +		void *(*get_next_fn)(const void *),
> +		void (*set_next_fn)(void *, void *),
> +		int (*compare_fn)(const void *, const void *))
> +{
> +	unsigned long l;
> +
> +	if (!list)
> +		return NULL;
> +	for (l = 1; ; l *= 2) {
> +		void *curr;
> +		struct mergesort_sublist p, q;
> +
> +		p.ptr = list;
> +		q.ptr = get_nth_next(p.ptr, l, get_next_fn);
> +		if (!q.ptr)
> +			break;
> +		p.len = q.len = l;
> +
> +		if (compare_fn(p.ptr, q.ptr) > 0)
> +			list = curr = pop_item(&q, get_next_fn);
> +		else
> +			list = curr = pop_item(&p, get_next_fn);
> +
> +		while (p.ptr) {
> +			while (p.len || q.len) {
> +				void *prev = curr;
> +
> +				if (!p.len)
> +					curr = pop_item(&q, get_next_fn);
> +				else if (!q.len)
> +					curr = pop_item(&p, get_next_fn);
> +				else if (compare_fn(p.ptr, q.ptr) > 0)
> +					curr = pop_item(&q, get_next_fn);
> +				else
> +					curr = pop_item(&p, get_next_fn);
> +				set_next_fn(prev, curr);
> +			}
> +			p.ptr = q.ptr;
> +			p.len = l;
> +			q.ptr = get_nth_next(p.ptr, l, get_next_fn);
> +			q.len = q.ptr ? l : 0;
> +
> +		}
> +		set_next_fn(curr, NULL);
> +	}
> +	return list;
> +}

After seeing "I wrote it myself due to NIH", it strikes me a bit odd that you still used "start from bunch of singleton sublist, elongating twice per round as we go" structure from the original.

I wonder if it would be an improvement if you structured the loop so that:

 (1) the first sublist 'p' grabs as many elements in the ascending order
     as you find;

 (2) the second sublist 'q' begins at the end of the first sublist and
     grabs as many elements in the ascending order;

 (3) 'p' and 'q' are merge-sorted into the result list;

 (4) if your two sublists did not cover "list" in its entirety, process
     the remainder (i.e. where the second sublist stopped because of an
     unordered element) by going back to step (1); and

 (5) if you did not need to jump back to step (1) from step (4), then you
     had only two sublists (or less), so the result is sorted.  Otherwise,
     the result now has fewer ascending sublists than the original, so go
     back to (1) and iterate.

If the input is in a random order, this may end up doing the same number of iterations as the original, but if the input is mostly sorted, wouldn't it allow us to take advantage of the fact by starting with a longer sublist in the earlier rounds?