Avoid O(n^2) complexity when building a sorted `string_list` by
constructing it unsorted and sorting it afterward, reducing the
complexity to O(n log n).
Signed-off-by: Meet Soni <meetsoni3017@xxxxxxxxx>
---
merge-recursive.c | 14 ++++----------
1 file changed, 4 insertions(+), 10 deletions(-)
diff --git a/merge-recursive.c b/merge-recursive.c
index 5dfaf32b2c..c43b79e6ef 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -2757,24 +2757,18 @@ static int process_renames(struct merge_options *opt,
struct string_list b_by_dst = STRING_LIST_INIT_NODUP;
const struct rename *sre;
- /*
- * FIXME: As string-list.h notes, it's O(n^2) to build a sorted
- * string_list one-by-one, but O(n log n) to build it unsorted and
- * then sort it. Note that as we build the list, we do not need to
- * check if the existing destination path is already in the list,
- * because the structure of diffcore_rename guarantees we won't
- * have duplicates.
- */
for (i = 0; i < a_renames->nr; i++) {
sre = a_renames->items[i].util;
- string_list_insert(&a_by_dst, sre->pair->two->path)->util
+ string_list_append(&a_by_dst, sre->pair->two->path)->util
= (void *)sre;
}
for (i = 0; i < b_renames->nr; i++) {
sre = b_renames->items[i].util;
- string_list_insert(&b_by_dst, sre->pair->two->path)->util
+ string_list_append(&b_by_dst, sre->pair->two->path)->util
= (void *)sre;
}
+ string_list_sort(&a_by_dst);
+ string_list_sort(&b_by_dst);
for (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) {
struct string_list *renames1, *renames2Dst;
base-commit: 9520f7d9985d8879bddd157309928fc0679c8e92
--
2.34.1
