From: Junio C Hamano <gitster@pobox.com>
Date: Mon, 09 Apr 2012 18:26:34 GMT
Subject: Re: [PATCH 1/3] add mergesort() for linked lists
Message-ID: <7vk41owylh.fsf@alter.siamese.dyndns.org>
In-Reply-To: <4F81F5E6.2070609@lsrfire.ath.cx>

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

> Am 05.04.2012 21:17, schrieb Junio C Hamano:
>> 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.
>
> It's just becasue the dumb bottom-up approach is the most simple way to
> implement merge sort.
> ...
> This optimization speeds up the pre-sorted case but slows down the case of
> a reversed pre-sorted list because we have to determine the length of the
> sublists each time,...

Ah, I somehow missed that point.  Thanks.