Three Way String Quicksort - Java

Complexity : 1.39 W N lg R.

Not a stable sort.

Source:

public class ThreeWSQS {
    
    public static int charAt(String s, int i){
        if(i<s.length()-1)return s.charAt(i); else return -1;
    }
    
    public static void sort(String[] s){
        sort(s, 0, s.length-1, 0);
    }
    
    private static void exch(String[] s, int a, int b){
        String ss = s[a];
        s[a] = s[b];
        s[b] = ss;
    }
    
    private static void sort(String[] s, int lo, int hi, int d){
        if(hi<=lo)return;
        
        int lt = lo, gt = hi;
        int i = lo+1;
        int c = charAt(s[lo], d);
        
        while(i<=gt){
            int cc = charAt(s[i], d);
            if(cc<c)exch(s, lt++, i++);
            else if(cc>c)exch(s, i, gt--);
            else i++;
        }
        
        sort(s, lo, lt-1, d);
        if(c>=0)sort(s, lt, gt, d+1);
        sort(s, gt+1, hi, d);
    }
    
    public static void main(String[] args){
        String[] s = new String[]{"she", "sells", "seashells", "by", "the", "sea", "the", "shells", "she", "sells", "are", "surely", "seashells"};
        sort(s);
        for(String ss:s)System.out.println(ss);
    }
}

Output:

are
by
sea
seashells
seashells
sells
sells
she
she
shells
surely
the
the