Re: Some git performance measurements..

[Jakub Narebski <jnareb@gmail.com>]

On Fri, 30 Nov 2007, Linus Torvalds wrote:
> 
> On Fri, 30 Nov 2007, Jakub Narebski wrote:
>> 
>> Isn't there a better way to do this sorting? What is needed here is
>> (stable) _bucket_ sort / _pigeonhole_ sort (or counting sort), which
>> is O(n); quicksort is perhaps simpler to use, but I'm not sure if
>> faster in this situation.
> 
> Actually, I doubt you need to do any sorting at all: what would be easiest 
> would be to simply change "traverse_commit_list()" to use different lists 
> for different object types, and just output them in type order (semi-sane 
> order choice: commits first, then tags, then trees, and finally blobs).
> 
> Ta-daa! All done! Magic! No sorting required, because all the objects got 
> output in the right order without any extra sort phase!

Actually this algorithm has the fancy name of "pigeonhole sort" algorithm,
and is a subcase (special case) of bucket sort. Well, sort of, as there
is no final sorted list, only output in "sorted" order.

-- 
Jakub Narebski
Poland