String merge sort in Java

Question

This snippet is about sorting a set of strings using merge sort. However, this version is tailored for strings as it relies on lcp values:

Given two strings \$A\$ and \$B\$, \$lcp(A, B)\$ is the length of the longest prefix shared by both \$A\$ and \$B\$. The cool point to note here is that if you know at least a lower bound of \$lcp(A, B)\$ (say, \$k < lcp(A, B)\$), whenever comparing \$A\$ and \$B\$, you can skip the first \$k\$ characters, and this string merge sort relies on these values in order to speed up the computation.

StringMergesort.java:

package net.coderodde.util;

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 (left < leftBound && right < rightBound) {
            int leftLCP  = sourceLCPArray[left];
            int rightLCP = sourceLCPArray[right];

            if (leftLCP > rightLCP) {
                target[targetIndex] = source[left];
                targetLCPArray[targetIndex++] = sourceLCPArray[left++];
            } else if (rightLCP > leftLCP) {
                target[targetIndex] = source[right];
                targetLCPArray[targetIndex++] = sourceLCPArray[right++];
            } else {
                lcpCompare(source[left], source[right], leftLCP, result);

                if (result.cmpValue <= 0) {
                    target[targetIndex] = source[left];
                    targetLCPArray[targetIndex++] = sourceLCPArray[left++];
                    sourceLCPArray[right] = result.lcp;
                } else {
                    target[targetIndex] = source[right];
                    targetLCPArray[targetIndex++] = sourceLCPArray[right++];
                    sourceLCPArray[left] = result.lcp;
                }
            }
        }

        while (left < leftBound) {
            target[targetIndex] = source[left];
            targetLCPArray[targetIndex] = sourceLCPArray[left];
            targetIndex++;
            left++;
        }

        while (right < rightBound) {
            target[targetIndex] = source[right];
            targetLCPArray[targetIndex] = sourceLCPArray[right];
            targetIndex++;
            right++;
        }
    }

    public static void main(String[] args) {
        long seed = System.nanoTime();
        Random random = new Random(seed);
        String[] array1 = createRandomStringArray(500_000, 300, random);
        String[] array2 = array1.clone();

        System.out.println("Seed = " + seed);

        long startTime = System.nanoTime();
        Arrays.sort(array1);
        long endTime = System.nanoTime();

        System.out.format("Arrays.sort in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        startTime = System.nanoTime();
        StringMergesort.sort(array2);
        endTime = System.nanoTime();

        System.out.format("StringMergesort.sort in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        System.out.println("Arrays equal: " + Arrays.equals(array1, array2));
    }

    private static String[] createRandomStringArray(int size, 
                                                    int maxLength, 
                                                    Random random) {
        String[] ret = new String[size];

        for (int i = 0; i < size; ++i) {
            ret[i] = randomString(maxLength, random);
        }

        return ret;
    }

    private static String randomString(int maxLength, Random random) {
        int length = random.nextInt(maxLength + 1);
        StringBuilder sb = new StringBuilder(length);

        for (int i = 0; i < length; ++i) {
            sb.append((char)('a' + random.nextInt(ALPHABET_SIZE)));
        }

        return sb.toString();
    }    
}

My performance figures are:

Seed = 5896859395728
Arrays.sort in 1220.41 milliseconds.
StringMergesort.sort in 669.97 milliseconds.
Arrays equal: true

Is there anything to improve here? Once again, I would like to hear comments on naming conventions, coding style, performance, and optimisation opportunities.

Answer 1

(Had to sort out what I wanted from this code, leaving:)
What is your goal coding this? From the amount of explanation, it does not seem to be educational. From the embedded micro-benchmark, it might be benchmarking an implementation of LCP mergesort.
I've tried to follow some of the thoughts presented below on Ideone, sort of minimally invasive. (The doc-comments are barely readable without tool support - I used Eclipse Mars. I've taken it quite a bit further - too early to put that in the open.)

• Code should be commented - at least javadoc comments for public (and protected) members. (I'm still yearning for a quotable, easy to understand presentation of LCP merge-sort, esp. an intuition why the LCP handling in merge is sufficient, what string is the other one in common. Not quite easy enough: A. Eberle's thesis "3.1.1. LCP-Compare" and "3.1.2. Binary LCP-Merge [and] Mergesort" (pp. 19-22).)
• Consider making sortImpl an instance method (you didn't hide the constructor, anyway), instead of passing around the arrays (and the ComparisonResult) in each and every call; lcpCompare() too, while you're at it. (non-trivial)
• (Using a static sortImpl,) I'd drop auxArray: sortImpl(array.clone(), array, …, new ComparisonResult()).
• Cloning the array as opposed to instantiation deserves a comment
• interchanging the roles of source and target in the recursive calls in sortImpl deserves a comment.
• int k in lcpCompare() might be named from, prefixLength, mightDiffer or postPrefix.
• I'd much prefer sourceLCP/targetLCP over …LCPArray.
• I'd rather have index increment in the "copy rest of run loops" look consistent with the merge loop.
• I'm not sure my reasoning about the LCP handling in merge() is correct: please comment this part of your code. (and check the @param comments on Ideone)

(Roll-your-own micro benchmarks are even more dangerous than tool-supported ones - I don't intend to go into main() & co. any further.)

Answer 2

Use final:

public static void sort(final String[] array, final int fromIndex, final int toIndex) {
    if (toIndex - fromIndex < 2) {
        return;
    }

    final String[] auxArray = array.clone();
    final int[] sourceLCPArray = new int[auxArray.length];
    final int[] targetLCPArray = new int[auxArray.length];
    final ComparisonResult result = new ComparisonResult();

Change void returns into this. Use StringMergesort as an object.

Modify returns of mutable objects, such as in createRandomStringArray:

    String[] ret = new String[size];

    for (int i = 0; i < size; ++i) {
        ret[i] = randomString(maxLength, random);
    }

    return ret;

Less hazardous:

    final String[] ret = new String[size];

    for (int i = 0; i < size; ++i) {
        ret[i] = randomString(maxLength, random);
    }

    return Arrays.copyOf(ret,ret.length);