C# Alphanumeric Sorting

Alphanumeric sorting logically handles numbers in strings.

It makes sense to humans. For example, highway names like 50F and 100F will be sorted wrongly with ASCII sort. We implement an alphanumeric sorting method.

ASCII Sort:

100F
50F
SR100
SR9

Alphanumeric Sort:

50F
100F
SR9
SR100

Example. First we use the alphanumeric sorting comparer (AlphanumComparatorFast) to deal with strings containing numbers and regular characters in a human-friendly order. It is different from alphabetic, ASCII or numeric sorting.

Note: This algorithmic approach is used in most file managers, and is useful on highway names.

C# program that uses comparator

using System;
using System.Collections;

class Program
{
    static void Main()
    {
	string[] highways = new string[]
	{
	    "100F",
	    "50F",
	    "SR100",
	    "SR9"
	};
	//
	// We want to sort a string array called highways in an
	// alphanumeric way. Call the static Array.Sort method.
	//
	Array.Sort(highways, new AlphanumComparatorFast());
	//
	// Display the results
	//
	foreach (string h in highways)
	{
	    Console.WriteLine(h);
	}
    }
}

Output

50F
100F
SR9
SR100

IComparer. Here we see the comparator for alphanumeric sorting. I optimized this version of the code. It is over 40% faster on most data sets. It has reduced memory usage and far better performance. It is accurate in my limited testing.

The IComparer implementation returns an integer. This result indicates which string comes first. It walks through both strings in a single loop. It tries to find equivalent chunks of those two strings at a position.

And: It uses char arrays for performance. Char arrays often improve string append performance in the .NET Framework.

Char Array

It uses two comparisons. It selects either an alphabetical comparison or a numeric comparison, depending on the chunk type. Next, it uses CompareTo, which indicates whether the first object is bigger or smaller than the second object.

CompareTo

Implementation of IComparer: C#

public class AlphanumComparatorFast : IComparer
{
    public int Compare(object x, object y)
    {
	string s1 = x as string;
	if (s1 == null)
	{
	    return 0;
	}
	string s2 = y as string;
	if (s2 == null)
	{
	    return 0;
	}

	int len1 = s1.Length;
	int len2 = s2.Length;
	int marker1 = 0;
	int marker2 = 0;

	// Walk through two the strings with two markers.
	while (marker1 < len1 && marker2 < len2)
	{
	    char ch1 = s1[marker1];
	    char ch2 = s2[marker2];

	    // Some buffers we can build up characters in for each chunk.
	    char[] space1 = new char[len1];
	    int loc1 = 0;
	    char[] space2 = new char[len2];
	    int loc2 = 0;

	    // Walk through all following characters that are digits or
	    // characters in BOTH strings starting at the appropriate marker.
	    // Collect char arrays.
	    do
	    {
		space1[loc1++] = ch1;
		marker1++;

		if (marker1 < len1)
		{
		    ch1 = s1[marker1];
		}
		else
		{
		    break;
		}
	    } while (char.IsDigit(ch1) == char.IsDigit(space1[0]));

	    do
	    {
		space2[loc2++] = ch2;
		marker2++;

		if (marker2 < len2)
		{
		    ch2 = s2[marker2];
		}
		else
		{
		    break;
		}
	    } while (char.IsDigit(ch2) == char.IsDigit(space2[0]));

	    // If we have collected numbers, compare them numerically.
	    // Otherwise, if we have strings, compare them alphabetically.
	    string str1 = new string(space1);
	    string str2 = new string(space2);

	    int result;

	    if (char.IsDigit(space1[0]) && char.IsDigit(space2[0]))
	    {
		int thisNumericChunk = int.Parse(str1);
		int thatNumericChunk = int.Parse(str2);
		result = thisNumericChunk.CompareTo(thatNumericChunk);
	    }
	    else
	    {
		result = str1.CompareTo(str2);
	    }

	    if (result != 0)
	    {
		return result;
	    }
	}
	return len1 - len2;
    }
}

Discussion. Alphanumeric sorting is often not ideal. If you have data that is formatted in a specific, known way, you can first parse it. Then, create objects based on the data. Finally, we can sort those objects based on a property.

Tip: Using an object model may lead to clearer, simpler code. It may be easier to maintain. And it may execute faster.

However: An alphanumeric sorting implementation is helpful for many problems that may be less defined.

Summary. We sorted strings alphanumerically in a C# program. This results in a more natural presentation of lists for your users. Use this IComparer implementation for alphanumeric or natural sorting.

Review: This code is neither the fastest nor clearest. But it works for small applications. Its results are predictable.

Related Links