Writing a better natural sort (than mine)

Question

I added an answer to this question here: Sorting List<String> in C# which calls for a natural sort order, one that handles embedded numbers.

My implementation, however, is naive, and in lieu of all the posts out there about how applications doesn't handle Unicode correctly by assuming things (Turkey test anyone?), I thought I'd ask for help writing a better implementation. Or, if there is a built-in method of .NET, please tell me :)

My implementation for the answer in that question just goes through the strings, comparing character by character, until it encounters a digit in both. Then it extracts consecutive digits from both strings, which can result in varying lengths, pads the shortest with leading zeroes, and then compares.

However, there's problems with it.

For instance, what if you in string x have two codepoints which together make the character È, but in the other string you have just one codepoint, the one that is that character.

My algorithm would fail on those, since it would treat the diacritic codepoint as a single character, and compare it to the È from the other string.

Can anyone guide me towards how to handle this properly? I want support for specifying a CultureInfo object to handle language problems, like comparing "ss" with "ß" in Germany, and similar things.

I think I need to get my code to enumerate over "real characters" (I don't know the real term here) instead of individual codepoints.

What's the right approach to this?

Also, if "natural" means "the way humans expect it to work", I would add the following things to ponder:

• What about dates and times?
• What about floating point values?
• Are there other sequences which are considered "natural"?
  • How far should this be stretched? (Eeny, meeny, miny, moe)

Answer 1

This is already available in Windows, the shell uses natural sort order when arranging the files in an Explorer window. The comparison function it uses is exported and available to any program, at least since Windows 2000. While P/Invoke isn't the greatest solution, it does have the considerable advantage of having been tested billions of times in the past 10 odd years. And sorting strings in a way that the user is already well familiar with.

Handling diacritics is already part of .NET, the string.Normalize() method takes care of it.

Here's a sample program that uses it, it properly sorts the strings as requested in the original thread:

using System;
using System.Collections.Generic;
using System.Runtime.InteropServices;

class Program {
    static void Main(string[] args) {
        string[] arr = new string[] { "1", "5", "3", "6", "11", "9", "NUM1", "NUM0" };
        Array.Sort(arr, new LogicalComparer());
        foreach (string s in arr) Console.WriteLine(s);
        Console.ReadLine();
    }
}
class LogicalComparer : IComparer<string> {
    public int Compare(string x, string y) {
        return StrCmpLogicalW(x.Normalize(), y.Normalize());
    }
    [DllImport("shlwapi.dll", CharSet = CharSet.Unicode, ExactSpelling = true)]
    private static extern int StrCmpLogicalW(string s1, string s2);
}