On Thu, Feb 13, 2025 at 1:00 AM Meet Soni <meetsoni3017@xxxxxxxxx> wrote:
>
> Avoid O(n^2) complexity in `process_renames()` 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 | 15 +++++++--------
> 1 file changed, 7 insertions(+), 8 deletions(-)
>
> diff --git a/merge-recursive.c b/merge-recursive.c
> index 5dfaf32b2c..884ccf99a5 100644
> --- a/merge-recursive.c
> +++ b/merge-recursive.c
> @@ -2758,23 +2758,22 @@ static int process_renames(struct merge_options *opt,
> 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.
> + * 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;
> --
> 2.34.1
This version looks good to me.
