natural sort - Java String Number Comparator

Question

I have a method returning a list of String that need to be sorted. However, I'm running into the old String number sorting issue and was wondering if any one could assist with a Comparator implementation or point me in the direction of one.

The list is going to return something list this:

State Lower Legislative District 1
State Lower Legislative District 11
State Lower Legislative District 12
...
State Lower Legislative District 2
...
State Lower Legislative District 100
...
State Upper Legislative District 1
State Upper Legislative District 11
...

So, first I need to do a basic String sort, but then I need to sort by the number. The number to sort on should always trail, and may be 2 or 3 digits.

(Edit) My initial thought is to split the string on space, run StringUtils.isNumeric on the number portion, then sort. However, it seems a bit of a kludge to me.

Can anyone assist?

Answer 1

I wrote a variation on String.CompareTo that compares the length of numbers found in the two strings. When encounting two numbers of the same length the alphanumeric compare is resumed as normal. It also skips leading zeros.

public static int compareNatural(String a, String b) {
    int la = a.length();
    int lb = b.length();
    int ka = 0;
    int kb = 0;
    while (true) {
        if (ka == la)
            return kb == lb ? 0 : -1;
        if (kb == lb)
            return 1;
        if (a.charAt(ka) >= '0' && a.charAt(ka) <= '9' && b.charAt(kb) >= '0' && b.charAt(kb) <= '9') {
            int na = 0;
            int nb = 0;
            while (ka < la && a.charAt(ka) == '0')
                ka++;
            while (ka + na < la && a.charAt(ka + na) >= '0' && a.charAt(ka + na) <= '9')
                na++;
            while (kb < lb && b.charAt(kb) == '0')
                kb++;
            while (kb + nb < lb && b.charAt(kb + nb) >= '0' && b.charAt(kb + nb) <= '9')
                nb++;
            if (na > nb)
                return 1;
            if (nb > na)
                return -1;
            if (ka == la)
                return kb == lb ? 0 : -1;
            if (kb == lb)
                return 1;

        }
        if (a.charAt(ka) != b.charAt(kb))
            return a.charAt(ka) - b.charAt(kb);
        ka++;
        kb++;
    }
}