NaturalStringComparer returns 0 for different strings like "file5" and "file005", so SortedSet silently drops them and SortedDictionary throws on Add #59

What's wrong

NaturalStringComparer.Compare returns 0 whenever every chunk compares equal. Numeric chunks are compared by value after leading zeros are stripped. Different strings therefore compare as equal when they differ only in leading zeros or in digit script:

The only ordinal check is the x == y short-circuit at the top of Compare. Nothing breaks the tie after the chunk loop.

Reproduction (ktsu.Sorting from NuGet, net10.0)

var c = new NaturalStringComparer();

var set = new SortedSet<string>(c) { "file5.txt", "file005.txt", "file05.txt" };
// set.Count == 1  → "file005.txt" and "file05.txt" were silently dropped

var d = new SortedDictionary<string, int>(c);
d["v1"] = 1;
d.Add("v01", 2);
// ArgumentException: An item with the same key has already been added. Key: [v01, 2]

var a = new[] { "b05", "a", "b5" }; Array.Sort(a, c);  // a, b05, b5
var b = new[] { "b5", "a", "b05" }; Array.Sort(b, c);  // a, b5, b05
// Same set of inputs, different output depending on input order

Why it matters

The main use for a natural comparer is sorting file names, versions, and similar user-visible keys, where img1.png and img01.png can both exist. Returning 0 for distinct strings causes three problems:

• Silent data loss. SortedSet<string>, SortedList, SortedDictionary, and ImmutableSortedSet treat the two names as the same key. Files disappear from a listing, and nothing reports an error.
• Crashes. SortedDictionary.Add / SortedList.Add throw on keys that are actually distinct.
• Nondeterministic order. Array.Sort / List.Sort are unstable, so the relative order of b5 and b05 depends on the input order. UI lists can reshuffle between refreshes.

IComparer<T> consumers expect Compare(x, y) == 0 only for strings they should treat as identical. Windows' StrCmpLogicalW (Explorer's natural sort) orders 5 and 05 differently for the same reason.

Suggested fix

Keep the natural ordering as the primary key, and add a deterministic tie-break when it reports equality:

// after the chunk loop, instead of returning the length comparison directly:
int chunkCountComparison = xMatches.Length.CompareTo(yMatches.Length);
if (chunkCountComparison != 0)
{
	return chunkCountComparison;
}

// Numerically equal but textually different (leading zeros, digit script): break the tie
// ordinally so distinct strings never compare equal.
return string.CompareOrdinal(x, y);

"file5" and "file005" stay adjacent, and neither can now sort between file4 and file6 on the wrong side. A slightly nicer secondary key is "fewer leading zeros first, then ordinal", which puts file5 before file05 before file005. The ordinal fallback is the minimum needed.

Acceptance criteria

• Compare(x, y) == 0 if and only if string.Equals(x, y, StringComparison.Ordinal) (nulls aside).
• A SortedSet<string> built with the comparer from {"file5", "file05", "file005"} has Count == 3.
• Sorting any permutation of {"a", "b5", "b05"} gives the same output.
• The existing tests that assert 0 for numerically equal chunks (Compare_StringsWithLeadingZeros_HandledCorrectly, Compare_NonAsciiDigits_EqualValuesAreEqual, Compare_NonAsciiLeadingZeros_NormalizedLikeAsciiZeros) are updated to assert a nonzero, antisymmetric result. Only the tie-break changes; numeric ordering against other values stays the same.