Huddled Masses

The basic problem is: sometimes you have a set of strings that have numbers in them that you’re displaying in a list somewhere in your UI. For example, file names like the photos from your camera, or product archives with version numbers …

Since Windows XP, users have gotten used to having these numbers sorted into a natural order (of course, Mac has had this since 1996, and in a format that makes it an automatic string sort replacement for all applications) but the .NET Framework, although it has new sorting abilities in .NET 2, still doesn’t have an equivalent to the Windows XP StrCmpLogicalW. There are implementations in many languages here but none for .NET ... and finally, there is a C# attempt on CodeProject, but it explicitly states it doesn’t return the same results as the Windows XP version, whereas the version that follows does.

I did some performance testing … ran 9 comparisons in a loop 100,000 times (total of 900,000 comparisons, with the same 3 strings in every combination (including comparing identical strings)

The bottom line is: in a worst-case … my algorithm takes 1/3 as long as using PInvoke to call the API method on XP, in a best case it’s much, much better than that, but never anywhere close to using the built-in CLR compares which ignore numbers.

Test 1 with numerical strings:

• Using my compare: 00:00:02.6407095
• Using StringCompare: 00:00:00.1093785

• Using StrCmpLogicalW: 00:00:06.6095865

Test 2 with non-numerical strings:

• Using my compare: 00:00:00.5937690
• Using StringCompare: 00:00:00.1093785

• Using StrCmpLogicalW: 00:00:06.6095865

I can probably speed this up using managed C++ because of the pointer arithmetic instead of needing to use array access for the characters in the strings, so I’ll most likely re-do it later.

I’ve got to figure out what in my blogging tool it screwing up the source code… in the meantime, download here

2 Responses to “Sorting Strings Naturally”