## Thursday, December 3, 2015

### 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