On 11/21/2014 05:44 PM, Junio C Hamano wrote: > On Fri, Nov 21, 2014 at 6:09 AM, Michael Haggerty <mhagger@xxxxxxxxxxxx> wrote: >> Inserting items into a list in sorted order is O(N^2) whereas >> appending them unsorted and then sorting the list all at once is >> O(N lg N). >> >> string_list_insert() also removes duplicates, and this change loses >> that functionality. But the strings in this list, which ultimately >> come from a for_each_ref() iteration, cannot contain duplicates. >> > > A similar conversion in other places we may do in the future > might find a need for an equivalent to "-u" option of "sort" in the > string_list_sort() function, but the above nicely explains why > it is not necessary for this one. Good. The only reason to integrate "-u" functionality into the sort would be if one expects a significant fraction of entries to be duplicates, in which case the sort could be structured to discard duplicates as it works, thereby reducing the work needed for the sort. I can't think of such a case in our code. Otherwise, calling sort_string_list() followed by string_list_remove_duplicates() should be just as clear and approximately as efficient. A couple of times I've also felt that an all-purpose *stable* sort would be convenient (though I can't remember the context offhand). I don't think we have such a thing. > Eh, why is that called sort_string_list()? Perhaps it is a good > opening to introduce string_list_sort(list, flag) where flag would > be a bitmask that represents ignore-case, uniquify, etc., and > then either deprecate the current one or make it a thin wrapper > of the one that is more consistently named. I agree. Indeed, I typed that function's name wrong once when constructing this patch. It would be better to name it consistently with the other string_list_*() functions. I put it on my todo list (but don't let that dissuade somebody else from doing it). Michael -- Michael Haggerty mhagger@xxxxxxxxxxxx -- 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