[RFC PATCH 0/2] merge-recursive: optimize time complexity

[Meet Soni <meetsoni3017@gmail.com>]

changes in this version:
    - Updated comment and commit message as per review.
    - Added another commit implementing optimization logic.
    - added an RFC tag since, if the changes in 2nd commit are
      appropriate, we can apply similar logic in other places as
      well.

Meet Soni (2):
  merge-recursive: optimize time complexity for process_renames
  merge-recursive: optimize time complexity for get_unmerged

 merge-recursive.c | 25 ++++++++++++-------------
 1 file changed, 12 insertions(+), 13 deletions(-)

Range-diff:
1:  ec96e4010e ! 1:  c7dca6e971 merge-recursive: optimize string_list construction
    @@ Metadata
     Author: Meet Soni <meetsoni3017@gmail.com>
     
      ## Commit message ##
    -    merge-recursive: optimize string_list construction
    +    merge-recursive: optimize time complexity for process_renames
     
    -    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).
    +    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@gmail.com>
     
      ## merge-recursive.c ##
     @@ merge-recursive.c: 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.
    --	 */
    ++	 * 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
-:  ---------- > 2:  78a007be7d merge-recursive: optimize time complexity for get_unmerged
-- 
2.34.1