MSD radix sort in Java for parallel arrays - follow-up

Question

The previous and initial iteration at MSD radix sort in Java for parallel arrays.

Changes:

• Entry hides both the sort key and satellite datum in private final fields. Henceforth, they are accessed through a pair of getters.
• sortTopImpl is removed and replaced by sortImpl, which now can handle the sign bit as well.
• compareTo of Entry uses Long.compare.

(Demo.java is the same as in the last iteration.)

So, what do you think?

Arrays.java:

package net.coderodde.util;

public class Arrays {

    private static final int BITS_PER_BUCKET = 8;
    private static final int BUCKETS = 1 << BITS_PER_BUCKET;
    private static final int BUCKET_MASK = BUCKETS - 1;
    private static final long SIGN_MASK = 1L << 63;
    private static final int MERGESORT_THRESHOLD = 4096;

    public static final <E> void sort(final Entry<E>[] array,
                                      final int fromIndex,
                                      final int toIndex) {
        if (toIndex - fromIndex < 2) {
            // Trivially sorted or indices ass-backwards.
            return;
        }

        final Entry<E>[] buffer = array.clone();
        sortImpl(array, buffer, 0, fromIndex, toIndex);
    }

    public static final <E> void sort(final Entry<E>[] array) {
        sort(array, 0, array.length);
    }

    public static final <E extends Comparable<? super E>> 
        boolean isSorted(final E[] array, 
                         final int fromIndex,
                         final int toIndex) {
        for (int i = fromIndex; i < toIndex - 1; ++i) {
            if (array[i].compareTo(array[i + 1]) > 0) {
                return false;
            }
        }

        return true;
    }

    public static final <E extends Comparable<? super E>>
        boolean isSorted(final E[] array) {
        return isSorted(array, 0, array.length);       
    }

    public static final <E> boolean areEqual(final Entry<E>[]... arrays) {
        for (int i = 0; i < arrays.length - 1; ++i) {
            if (arrays[i].length != arrays[i + 1].length) {
                return false;
            }
        }

        for (int i = 0; i < arrays[0].length; ++i) {
            for (int j = 0; j < arrays.length - 1; ++j) {
                if (arrays[j][i] != arrays[j + 1][i]) {
                    return false;
                }
            }
        }

        return true;
    }

    /**
     * This static method sorts the entry array by bytes that are not
     * most-significant.
     * 
     * @param <E> the type of satellite data in the entry array.
     * @param source the source array.
     * @param target the target array.
     * @param byteIndex the index of the byte to use as the sorting key. 0 
     * represents the least-significant byte.
     * @param fromIndex the least index of the range to sort.
     * @param toIndex the index one past the greatest index of the range to 
     * sort.
     */
    private static <E> void sortImpl(final Entry<E>[] source,
                                     final Entry<E>[] target,
                                     final int recursionDepth,
                                     final int fromIndex,
                                     final int toIndex) {
        // Try merge sort.
        if (toIndex - fromIndex <= MERGESORT_THRESHOLD) {
            // If 'even' is true, the sorted ranged ended up in 'source'.
            final boolean even = mergesort(source, target, fromIndex, toIndex);

            if (even) {
                // source contains the sorted bucket.
                if ((recursionDepth & 1) == 1) {
                    // byteIndex = 6, 4, 2, 0.
                    // source is buffer, copy to target.
                    System.arraycopy(source,
                                     fromIndex, 
                                     target,
                                     fromIndex, 
                                     toIndex - fromIndex);
                }
            } else {
                // target contains the sorted bucket.
                if ((recursionDepth & 1) == 0) {
                    // byteIndex = 5, 3, 1.
                    // target is buffer, copy to source.
                    System.arraycopy(target, 
                                     fromIndex,
                                     source, 
                                     fromIndex, 
                                     toIndex - fromIndex);
                }
            }

            return;
        }

        final int[] bucketSizeMap = new int[BUCKETS];
        final int[] startIndexMap = new int[BUCKETS];
        final int[] processedMap  = new int[BUCKETS];

        // Compute the size of each bucket.
        for (int i = fromIndex; i < toIndex; ++i) {
            bucketSizeMap[getBucket(source[i].key(), recursionDepth)]++;
        }

        // Initialize the start index map.
        startIndexMap[0] = fromIndex;

        // Compute the start index map in its entirety.
        for (int i = 1; i != BUCKETS; ++i) {
            startIndexMap[i] = startIndexMap[i - 1] +
                               bucketSizeMap[i - 1];
        }

        // Insert the entries from 'source' into their respective 'target'.
        for (int i = fromIndex; i < toIndex; ++i) {
            final Entry<E> e = source[i];
            final int index = getBucket(source[i].key(), recursionDepth);
            target[startIndexMap[index] + processedMap[index]++] = e;
        }

        if (recursionDepth == 7) {
            // There is nowhere to recur, return.
            return;
        }

        // Recur to sort each bucket.
        for (int i = 0; i != BUCKETS; ++i) {
            if (bucketSizeMap[i] != 0) {
                sortImpl(target,
                         source,
                         recursionDepth + 1,
                         startIndexMap[i],
                         startIndexMap[i] + bucketSizeMap[i]);
            }
        }
    }

    /**
     * Sorts the range <code>[fromIndex, toIndex)</code> between the arrays
     * <code>source</code> and <code>target</code>.
     * 
     * @param <E> the type of entries' satellite data.
     * @param source the source array; the data to sort is assumed to be in this
     * array.
     * @param target acts as an auxiliary array.
     * @param fromIndex the least component index of the range to sort.
     * @param toIndex <code>toIndex - 1</code> is the index of the rightmost
     * component in the range to sort.
     * @return <code>true</code> if there was an even amount of merge passes,
     * which implies that the sorted range ended up in <code>source</code>.
     * Otherwise <code>false</code> is returned, and the sorted range ended up
     * in the array <code>target</code>.
     */
    private static final <E> boolean mergesort(final Entry<E>[] source,
                                               final Entry<E>[] target,
                                               final int fromIndex,
                                               final int toIndex) {
        final int RANGE_LENGTH = toIndex - fromIndex;

        Entry<E>[] s = source;
        Entry<E>[] t = target;

        int passes = 0;

        for (int width = 1; width < RANGE_LENGTH; width <<= 1) {
            ++passes;
            int c = 0;

            for (; c < RANGE_LENGTH / width; c += 2) {
                int left = fromIndex + c * width;
                int right = left + width;
                int i = left;

                final int leftBound = right;
                final int rightBound = Math.min(toIndex, right + width);

                while (left < leftBound && right < rightBound) {
                    t[i++] = s[right].key() < s[left].key() ?
                             s[right++] :
                             s[left++];
                }

                while (left < leftBound)   { t[i++] = s[left++]; }
                while (right < rightBound) { t[i++] = s[right++]; }
            }

            if (c * width < RANGE_LENGTH) {
                for (int i = fromIndex + c * width; i < toIndex; ++i) {
                    t[i] = s[i];
                }
            }

            final Entry<E>[] tmp = s;
            s = t;
            t = tmp;
        }

        return (passes & 1) == 0;
    }

    private static int getPassAmount(int length) {
        if (length < 1) {
            // Should not get here.
            length = 1;
        }

        return 32 - Integer.numberOfLeadingZeros(length - 1);
    }

    private static final int getBucket(final long key, 
                                       final int recursionDepth) {
        final int bitShift = 64 - (recursionDepth + 1) * BITS_PER_BUCKET;
        return (int)((key ^ SIGN_MASK) >>> bitShift) & BUCKET_MASK;
    }
}

Entry.java:

package net.coderodde.util;

/**
 * The wrapper class holding a satellite datum and the key.
 *
 * @param <E> the type of a satellite datum.
 */
public final class Entry<E> implements Comparable<Entry<E>> {

    /**
     * The sorting key.
     */
    private final long key;

    /**
     * The satellite data.
     */
    private final E satelliteData;

    /**
     * Constructs a new <code>Entry</code> with key <code>key</code> and 
     * the satellite datum <code>satelliteData</code>.
     * 
     * @param key the key of this entry.
     * @param satelliteData the satellite data associated with the key.
     */
    public Entry(final long key, final E satelliteData) {
        this.key = key;
        this.satelliteData = satelliteData;
    }

    public long key() {
        return key;
    }

    public E satelliteData() {
        return satelliteData;
    }

    /**
     * Compares this <code>Entry</code> with another.
     * 
     * @param o the entry to compare against.
     * 
     * @return a negative value if this entry's key is less than that of 
     * <code>o</code>, a positive value if this entry's key is greater than that
     * of <code>o</code>, or 0 if the two keys are equal.
     */
    @Override
    public int compareTo(Entry<E> o) {
        return Long.compare(key, o.key);
    }
}

Answer 1

Nice improvement. There is much less to review now, which is a good thing. Similarly, because there is less, you can also see things that the previous review missed.

Naming

While Arrays is a good name for this class, it is too good. It conflicts with java.util.Arrays and it makes sense to name it differently so people can conveniently use both the java.util and your version of Arrays at the same time.

Equals

Consider this code here which is from the areEquals(...) method:

    for (int i = 0; i < arrays[0].length; ++i) {
        for (int j = 0; j < arrays.length - 1; ++j) {
            if (arrays[j][i] != arrays[j + 1][i]) {
                return false;
            }
        }
    }

The code compares each member of each array with the members in the 'next' array. This should be using equals rather than identity == compares. Additionally, to handle null values in the array, it would make sense to use the Objects.equals(..., ...) method from java.util. The inner condition would be:

if (!Objects.equals(arrays[j][i], arrays[j+1][i])) {
    return false;
}

As a side note, one possible optimization would be to calculate a hash code for the entire arrays before comparing them. This makes sense if you expect there to be differences more often than you expect them to be equals. If the hashCodes are different then they can never be equals:

int targetHash = java.util.Arrays.hashCode(arrays[j]);

then compare that to the hashCodes of the other arrays. Only if they are all the same do you need to do the actual comparisons.

Again, this only makes sense if you expect there to be differences more often than not.

Sorting

In sortImpl I would really prefer if the contents of the merge sort block were put in to a separate method. Having parts of two sorts in one method is... messy. in this case, the clean=up swap after the merge (if needed), is messy. I would extract that all in to a method that takes the recursion depth as an input as well, and calls the mergeSort and does the cleanUp. This way the radix-sort method becomes:

if (toIndex - fromIndex <= MERGESORT_THRESHOLD) {
    mergeSortAndClean(...., recursionDepth);
    return;
}

The documentation here is lacking:

    if (recursionDepth == 7) {
        // There is nowhere to recur, return.
        return;
    }

We should have a reminder why the 7 is 'magic', or it should be a proper constant. I can't really remember the significance..... note that the JavaDoc on your method still refers to byteIndex, and should be for the recursionDepth instead....

Also, I believe the recursionDepth == 7 will never happen because the mergesort threshold will happen first, right?

All in all, it looks good though. Nicely done. I hope it makes more sense to you now too.