Re: [PATCH] wt-status: avoid quadratic insertion for untracked paths

On Fri, Jul 17, 2026 at 1:24 PM Jeff King [off-list ref] 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.