From: Sahitya Chandra <sahityajb@gmail.com>
Date: Fri, 17 Jul 2026 14:40:55 GMT
Subject: Re: [PATCH] wt-status: avoid quadratic insertion for untracked paths
Message-ID: <CAP=WS+uWJJ3MY9K3JX-PQo_pKimNtyCO_fTdFsA=AXqbzO-bLg@mail.gmail.com>
In-Reply-To: <20260717075449.GA1832790@coredump.intra.peff.net>

On Fri, Jul 17, 2026 at 1:24 PM Jeff King <peff@peff.net> wrote:
> Yeah, I had the same question, and tried for a moment to produce an
> example before realizing that it probably is theoretical. If we are
> feeding the entries in pre-sorted order then the insert is always O(1).
>
> I think it's still worth doing this, though, as it makes the result much
> more obvious to analyze. I think it could even be O(n) if the sort
> implementation is optimized under the hood for pre-sorted inputs.

Thanks, that makes sense. I updated v2 to avoid claiming this is a
current O(n^2) problem and instead frame it as making the append, sort,
and deduplicate steps explicit.

I also switched to string_list_sort_u() as Patrick suggested.