//michael cheung
//had after school activity so is late by 4 hours
import java.util.Arrays;
import java.util.Random;
public class StringMergesort {
private static final int ALPHABET_SIZE = 26;
private static final class ComparisonResult {
int cmpValue;
int lcp;
}
public static void sort(String[] array) {
sort(array, 0, array.length);
}
public static void sort(String[] array, int fromIndex, int toIndex) {
if (toIndex - fromIndex < 2) {
return;
}
String[] auxArray = array.clone();
int[] sourceLCPArray = new int[auxArray.length];
int[] targetLCPArray = new int[auxArray.length];
ComparisonResult result = new ComparisonResult();
sortImpl(auxArray,
array,
sourceLCPArray,
targetLCPArray,
fromIndex,
toIndex,
result);
}
private static void lcpCompare(String a,
String b,
int k,
ComparisonResult comparisonResult) {
int length = Math.min(a.length(), b.length());
for (int i = k; i < length; ++i) {
char ach = a.charAt(i);
char bch = b.charAt(i);
if (ach != bch) {
comparisonResult.cmpValue = Character.compare(ach, bch);
comparisonResult.lcp = i;
return;
}
}
comparisonResult.lcp = length;
if (a.length() > length) {
comparisonResult.cmpValue = 1;
} else if (a.length() < length) {
comparisonResult.cmpValue = -1;
} else {
comparisonResult.cmpValue = 0;
}
}
private static void sortImpl(String[] source,
String[] target,
int[] sourceLCPArray,
int[] targetLCPArray,
int fromIndex,
int toIndex,
ComparisonResult result) {
int rangeLength = toIndex - fromIndex;
if (rangeLength < 2) {
return;
}
int middle = fromIndex + ((toIndex - fromIndex) >> 1);
sortImpl(target,
source,
targetLCPArray,
sourceLCPArray,
fromIndex,
middle,
result);
sortImpl(target,
source,
targetLCPArray,
sourceLCPArray,
middle,
toIndex,
result);
merge(source,
target,
sourceLCPArray,
targetLCPArray,
fromIndex,
middle - fromIndex,
toIndex - middle,
result);
}
private static void merge(String[] source,
String[] target,
int[] sourceLCPArray,
int[] targetLCPArray,
int offset,
int leftRangeLength,
int rightRangeLength,
ComparisonResult result) {
int left = offset;
int leftBound = offset + leftRangeLength;
int right = leftBound;
int rightBound = right + rightRangeLength;
int targetIndex = offset;
while (l...
