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 - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
