Merge sort implementation weirdly faster than system sort

Question

I wrote the following functions to merge sort an array of Comparables. It seems to work well (I am testing the output to make sure it is sorted). It takes about 2.5 sec for 10 million randomly generated strings. However, when I use the system sort by calling Arrays.sort(), it takes about 18 seconds. Why this huge discrepancy?

private static void merge(Comparable[] a, Comparable[] aux, int low, int mid, int high) {
 int i = low;
 int j = mid;
 for (int k = low; k <= high; k++) {
 aux[k] = a[i];
 }
 for (int k = low; k <= high; k++) {
 if (i < mid) {
 if (j > high) {
 a[k] = aux[i++];
 } else {
 if (aux[i].compareTo(aux[j]) <= 0) {
 a[k] = aux[i++];
 } else if (aux[i].compareTo(aux[j]) > 0) {
 a[k] = aux[j++];
 }
 }
 } else {
 a[k] = aux[j++];
 }
 }
}
private static void mergesort(Comparable[] a, Comparable[] aux, int start, int end) {
 int N = end - start + 1;
 if (N < 2) return;
 int lo = start;
 int mid = start + N/2;
 int hi = end;
 mergesort(a, aux, lo, mid-1);
 mergesort(a, aux, mid, hi);
 merge(a, aux, lo, mid, hi);
}
private static void msort(Comparable[] a) {
 int N = a.length;
 if (N < 2) return;
 Comparable[] aux = new Comparable[N];
 //System.arraycopy(a, 0, aux, 0, N);
 mergesort(a, aux, 0, N - 1);
}
private static boolean isSorted(Comparable[] a) {
 int N = a.length;
 if (N < 2) return true;
 for (int i = 1; i < N; i++) {
 if (a[i-1].compareTo(a[i]) > 0) {
 return false;
 }
 }
 return true;
}
private static String createRandString(int lo, int hi) {
 int len = myrandgen.uniform(lo, hi+1);
 StringBuilder sb = new StringBuilder();
 for (int i = 0; i < len; i++) {
 char ch = (char) myrandgen.uniform(97, 123);
 sb.append(ch);
 }
 return sb.toString();
}
private static void sortTester(int inputSize) {
 String[] s = new String[inputSize];
 for (int i = 0; i < inputSize; i++) {
 String t = createRandString(5,15);
 s[i] = t;
 }
 long start = System.currentTimeMillis();
 //Arrays.sort(s);
 msort(s);
 long end = System.currentTimeMillis();
 if (isSorted(s)) {
 System.out.println("Good Sort.");
 System.out.printf("Time taken: %d for %d elements.\n", end - start, inputSize);
 } else {
 System.out.println("Bad Sort.");
 }
}
/**
 * Unit tests merge sort.
 */
public static void main(String[] args) {
 sortTester(10000000);
}

• CAD97: The OpenJDK implementation guarantees O ( n log n )performance (this is a resource)

Answer 1

That's because your implementation is not correct. You have

private static void merge(Comparable[] a, Comparable[] aux, int low, int mid, int high) {
 int i = low;
 int j = mid;
 for (int k = low; k <= high; k++) {
 aux[k] = a[i];
 }
 for (int k = low; k <= high; k++) {
 ...

yet I believe you need:

private static void merge(Comparable[] a, Comparable[] aux, int low, int mid, int high) {
 int i = low;
 int j = mid;
 for (int k = low; k <= high; k++) {
 aux[k] = a[i++]; // <--- INCREMENT i
 }
 i = low; // <--- RESET i
 ...

The demonstration program is here.

The output is

Good Sort.
Time taken: 29846 for 10000000 elements.
Good.
Arrays.sort in 25226 ms.
true

Hope that helps.

• user3079275: Thanks, good catch. I just need to make it aux[k] = a[k] in the for loop.