MSD String Sort - Java

In MSD, we start the recursive sort from the most significant position in the strings. This method can handle variable length strings. An extra "-1" is considered at the end of each string.

Complexity (Frequency of operations : ) - 2NW

where W stands for the average width of the string. and N stands for the number of strings.

MSD is a stable sort.

Code -

public class MSDStringSort {
    static int R = 2<<8;
    
    public static void sort(String[] s){
        String[] aux = new String[s.length];
        int lo = 0, hi = s.length-1, at = 0;
        sort(s, aux, lo, hi, at);
    }
    
    private static int charAt(String s, int i){
        if(i<s.length())return s.charAt(i);
        else return -1;
    }
    
    private static void sort(String[] s, String[] aux, int lo, int hi, int at){
        
        if(hi<=lo)return;
        
        int[] count = new int[R+2];
        
        for(int i = lo; i <= hi; ++i)    count[charAt(s[i], at)+2]++;
        
        for(int i = 0; i < R+1; ++i)     count[i+1] += count[i];
        
        for(int i = lo; i <= hi; ++i)    aux[count[charAt(s[i], at)+1]++] = s[i];
        
        for(int i = lo; i <= hi; ++i)    s[i] = aux[i-lo];
        
        for(int r=0;r<R;++r) sort(s, aux, lo+count[r], lo+count[r+1]-1, at+1); 
    }
    
    public static void main(String[] args) throws Exception{ 
        
        String[] s = {"a", "aa", "ab", "abc", "d", "qq", "ff"};  
        sort(s);
        for(int i=0;i<s.length;++i) System.out.println(s[i]);
    }
}

Output -

a
aa
ab
abc
d
ff
qq