Junio C Hamano <gitster@xxxxxxxxx> writes: > David Kastrup <dak@xxxxxxx> writes: > >> Does anything speak against sorting the pathspecs? That is an O(n log >> n) operation, > > Not sorting is O(0) operation without losing cycles for the > normal case. I think you can sort first in that error handling > path to avoid O(n^2) but sorting upfront to remove duplicates > for every case is unnecessary bloat that penalizes sane callers. Not if you need to sort the file list anyway in order to merge it with the index. Of course, sorting patterns will not in all cases establish the order of their expansions. In any case, uniqueness should be establishable when matching to the index, regardless of whether this matching is done by sort&merge (probably the most efficient variant) or by binary search as it is done now if I understand correctly. I am just not happy with the ensuing binary _insertion_ as this is an O(nm) operation when inserting n elements into an m element data structure. A list merge is O(n+m), in contrast, and we can access the index sequentially. -- David Kastrup, Kriemhildstr. 15, 44793 Bochum - 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
