Alphanumeric sort

This C# sorting algorithm logically handles numbers in strings—it makes sense to humans. Highway names like 50F and 100F will be sorted wrongly with ASCII sort.

To sort while considering larger numbers (like 100) as single values, we can develop a simple parser. Then we sort on the parsed data, not just the raw chars.

Consider the ASCII and alphanumeric sorting results for some example strings. These could be highway names or any other terms that use both letters and digits.

' ASCII:

100F
50F
SR100
SR9

' Alphanumeric:

50F
100F
SR9
SR100

Example

First we use the alphanumeric sorting comparer (AlphanumComparator). We deal with strings containing numbers and regular characters in a human-friendly order.

Return The IComparer implementation returns an integer. This result indicates which string comes first.

Info The code walks through both strings in a single loop. It tries to find equivalent chunks of those 2 strings at a position.

Note It uses 2 comparisons and CompareTo. It selects either an alphabetical comparison or a numeric comparison, depending on the chunk type.

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

using System;
using System.Collections;

public class AlphanumComparator : 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 marker1 = 0;
        int marker2 = 0;

        // Walk through the strings with two markers.
        while (marker1 < s1.Length && marker2 < s2.Length)
        {
            // Collect char arrays.
            char[] chunk1 = GetChunk(ref marker1, s1);
            char[] chunk2 = GetChunk(ref marker2, s2);

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

            int result;
            if (char.IsDigit(chunk1[0]) && char.IsDigit(chunk2[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 s1.Length - s2.Length;
    }

    char[] GetChunk(ref int marker, string s)
    {
        // Walk through all following characters that are digits or
        // characters in a string starting at the appropriate marker.
        char[] space = new char[s.Length];
        int loc = 0;
        char c = s[marker];
        do
        {
            space[loc++] = c;
            marker++;

            if (marker < s.Length)
            {
                c = s[marker];
            }
            else
            {
                break;
            }
        } while (char.IsDigit(c) == char.IsDigit(space[0]));
        return space;
    }
}

class Program
{
    static void Main()
    {
        string[] highways = new string[] { "100F", "50F", "SR100", "SR9" };

        // Sort a string array called highways in an alphanumeric way.
        Array.Sort(highways, new AlphanumComparator());

        // ... Display the results.
        Console.WriteLine(string.Join(" ", highways));
    }
}
50F 100F SR9 SR100

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. So we sort a parsed representation.

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.

It is possible to strings alphanumerically. This results in a more natural presentation of lists for your users. Use this IComparer implementation for alphanumeric or natural sorting.