7
\$\begingroup\$

I was curious, how in-place radix sort compares to the variant which uses an auxiliary array in order to speed up the sorting. I implemented both and tested it against java.util.Arrays.sort(int[]).

Seed: 1439451337582
Radixsort.InPlace.sort in 12074 milliseconds.
Radixsort.sort in 6937 milliseconds.
Arrays.sort in 16316 milliseconds.
Arrays identical: true

What do you think?

Radixsort.java:

package net.coderodde.util;

import java.util.Arrays;

/**
 * This class implements a radix sort using an auxiliary array in order to speed
 * up sorting.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public class Radixsort {

    /**
     * The byte index of the most significant byte in each 32-bit integer.
     */
    private static final int MOST_SIGNIFICANT_BYTE_INDEX = 3;

    /**
     * The mask for manipulating the sign bit.
     */
    private static final int SIGN_BIT_MASK = 0x8000_0000;

    /**
     * The amount of bits per byte.
     */
    private static final int BITS_PER_BYTE = 8;

    /**
     * The mask for extracting the bucket index.
     */
    private static final int EXTRACT_BYTE_MASK = 0xff;

    /**
     * The amount of buckets considered for sorting.
     */
    private static final int BUCKET_AMOUNT = 256;

    /**
     * If the range length is less than this constant use 
     * {@link java.util.Arrays.sort} and exit.
     */
    private static final int QUICKSORT_THRESHOLD = 128;

    /**
     * This inner static class provides an in-place implementation of the radix
     * sort.
     */
    public static final class InPlace {

        /**
         * Sorts the range {@code array[fromIndex], array[fromIndex + 1], ...,
         * array[toIndex - 2], array[toIndex - 1]}.
         * 
         * @param array     the array holding the target range.
         * @param fromIndex the starting, inclusive index of the range.
         * @param toIndex   the ending, exclusive index of the range.
         */
        public static void sort(int[] array, int fromIndex, int toIndex) {
            if (toIndex - fromIndex < 2) {
                return;
            }

            sort(array, fromIndex, toIndex, MOST_SIGNIFICANT_BYTE_INDEX);
        }

        /**
         * Sorts the entire array.
         * 
         * @param array the array to sort.
         */
        public static void sort(int[] array) {
            sort(array, 0, array.length);
        }

        private static void sort(int[] array, 
                                 int fromIndex,
                                 int toIndex,
                                 int byteIndex) {
            if (toIndex - fromIndex < QUICKSORT_THRESHOLD) {
                Arrays.sort(array, fromIndex, toIndex);
                return;
            }

            int[] bucketSizeMap = new int[BUCKET_AMOUNT];

            // Count the size of each bucket.
            for (int i = fromIndex; i < toIndex; ++i) {
                bucketSizeMap[getBucketIndex(array[i], byteIndex)]++;
            }

            // Compute the map mapping each bucket into its start index.
            int[] startIndexMap = new int[BUCKET_AMOUNT];
            startIndexMap[0] = fromIndex;

            for (int i = 1; i < BUCKET_AMOUNT; ++i) {
                startIndexMap[i] = startIndexMap[i - 1] + bucketSizeMap[i - 1];
            }

            int[] processedMap = new int[BUCKET_AMOUNT];
            boolean[] bucketReadyMap = new boolean[BUCKET_AMOUNT];

            // Now move the elements to their proper buckets.
            for (int index = fromIndex; index < toIndex;) {
                int element = array[index];
                int elementBucketIndex = getBucketIndex(element, byteIndex);
                int targetIndex = startIndexMap[elementBucketIndex] +
                                   processedMap[elementBucketIndex];

                if (bucketReadyMap[elementBucketIndex] 
                        || index == targetIndex) {
                    ++index;
                } else {
                    int tmp = array[targetIndex];
                    array[targetIndex] = element;
                    array[index] = tmp;
                    processedMap[elementBucketIndex]++;
                }

                if (processedMap[elementBucketIndex] 
                        == bucketSizeMap[elementBucketIndex]) {
                    bucketReadyMap[elementBucketIndex] = true;
                }
            }

            // Recur to sorting the buckets.
            if (byteIndex > 0) {
                // If more bytes are available, recursively sort the buckets.
                for (int i = 0; i < BUCKET_AMOUNT; ++i) {
                    if (bucketSizeMap[i] != 0) {
                        sort(array, 
                             startIndexMap[i],
                             startIndexMap[i] + bucketSizeMap[i],
                             byteIndex - 1);
                    }
                }
            }
        }
    }

    /**
     * Sorts the range {@code array[fromIndex], array[fromIndex + 1], ...,
     * array[toIndex - 2], array[toIndex - 1]}.
     * 
     * @param array     the array holding the target range.
     * @param fromIndex the starting, inclusive index of the range.
     * @param toIndex   the ending, exclusive index of the range.
     */
    public static void sort(int[] array, int fromIndex, int toIndex) {
        if (toIndex - fromIndex < 2) {
            return;
        }

        sort(array,
             Arrays.copyOfRange(array, fromIndex, toIndex), 
             fromIndex,
             0,
             toIndex - fromIndex,
             MOST_SIGNIFICANT_BYTE_INDEX);
    }

    /**
     * Sorts the entire array.
     * 
     * @param array the array to sort.
     */
    public static void sort(int[] array) {
        sort(array, 0, array.length);
    }

    private static void sort(int[] source, 
                             int[] target,
                             int sourceOffset,
                             int targetOffset,
                             int rangeLength,
                             int byteIndex) {
        if (rangeLength < QUICKSORT_THRESHOLD) {
            Arrays.sort(source, sourceOffset, sourceOffset + rangeLength);

            if ((byteIndex & 1) == 0) {
                System.arraycopy(source, 
                                 sourceOffset, 
                                 target, 
                                 targetOffset, 
                                 rangeLength);
            }

            return;
        }

        int[] bucketSizeMap = new int[BUCKET_AMOUNT];

        // Count the size of each bucket.
        for (int i = sourceOffset; i < sourceOffset + rangeLength; ++i) {
            bucketSizeMap[getBucketIndex(source[i], byteIndex)]++;
        }

        // Compute the map mapping each bucket to its beginning index.
        int[] startIndexMap = new int[BUCKET_AMOUNT];

        for (int i = 1; i < BUCKET_AMOUNT; ++i) {
            startIndexMap[i] = startIndexMap[i - 1] + bucketSizeMap[i - 1];
        }

        // The map mapping each bucket index to amount of elements already put
        // in the bucket.
        int[] processedMap = new int[BUCKET_AMOUNT];

        for (int i = sourceOffset; i < sourceOffset + rangeLength; ++i) {
            int element = source[i];
            int bucket = getBucketIndex(element, byteIndex);
            target[targetOffset + startIndexMap[bucket] + 
                                   processedMap[bucket]++] = element;
        }

        if (byteIndex > 0) {
            // Recursively sort the buckets.
            for (int i = 0; i < BUCKET_AMOUNT; ++i) {
                if (bucketSizeMap[i] != 0) {
                    sort(target, 
                         source, 
                         targetOffset + startIndexMap[i],
                         sourceOffset + startIndexMap[i], 
                         bucketSizeMap[i], 
                         byteIndex - 1);
                }
            }
        }
    }

    /**
     * Returns the bucket index for {@code element} when considering 
     * {@code byteIndex}th byte within the element. The indexing starts from
     * the least significant bytes.
     * 
     * @param element   the element for which to compute the bucket index.
     * @param byteIndex the index of the byte to be considered.
     * @return the bucket index.
     */
    private static int getBucketIndex(int element, int byteIndex) {
        return ((byteIndex == MOST_SIGNIFICANT_BYTE_INDEX ? 
                 element ^ SIGN_BIT_MASK :
                 element) >>> (byteIndex * BITS_PER_BYTE)) & EXTRACT_BYTE_MASK;
    }

}

Demo.java:

import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;
import net.coderodde.util.Radixsort;

/**
 * This class implements a demonstration comparing the performance of the radix
 * sorts.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public class Demo {

    public static void main(String[] args) {
        long seed = System.currentTimeMillis();
        Random random = new Random(seed);

        int[] array1 = getRandomIntegerArray(100000000, random);
        int[] array2 = array1.clone();
        int[] array3 = array1.clone();

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

        long startTime = System.currentTimeMillis();
        Radixsort.InPlace.sort(array1, 3, array1.length - 4);
        long endTime = System.currentTimeMillis();

        System.out.println("Radixsort.InPlace.sort in " + (endTime - startTime) + 
                           " milliseconds.");

        startTime = System.currentTimeMillis();
        Radixsort.sort(array2, 3, array2.length - 4);
        endTime = System.currentTimeMillis();

        System.out.println("Radixsort.sort in " + (endTime - startTime) +
                           " milliseconds.");

        startTime = System.currentTimeMillis();
        Arrays.sort(array3, 3, array2.length - 4);
        endTime = System.currentTimeMillis();

        System.out.println("Arrays.sort in " + (endTime - startTime) + 
                           " milliseconds.");

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

    private static int[] getRandomIntegerArray(int size, Random random) {
        return IntStream.range(0, size).map((a) -> random.nextInt()).toArray();
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ I would have thought the out-of-place sort would use a LSB algorithm, which would be faster than the MSB algorithm. \$\endgroup\$ – JS1 Aug 13 '15 at 21:04
  • \$\begingroup\$ In order to qualify the inPlace vs outPlace, we would need to evaluate the memory costs :) Repeat the tests with hundreds of arrays of various sizes, so that the garbage collector start hurting. Then compare :) \$\endgroup\$ – Jan Oct 15 '15 at 13:57
  • \$\begingroup\$ Care to include a statement about the stability of InPlace.sort(int[])? \$\endgroup\$ – greybeard Apr 29 '18 at 15:29
  • \$\begingroup\$ @greybeard Not relevant since ints are not objects. \$\endgroup\$ – coderodde Apr 29 '18 at 16:24
2
\$\begingroup\$

Not much to say about this lovely well-documented code, it's very well written. Just some notes:

private static int getBucketIndex(int element, int byteIndex) {
    return ((byteIndex == MOST_SIGNIFICANT_BYTE_INDEX ? 
             element ^ SIGN_BIT_MASK :
             element) >>> (byteIndex * BITS_PER_BYTE)) & EXTRACT_BYTE_MASK;
}

The return statement looks ugly and hard to read. Turn it into an if statement:

private static int getBucketIndex(int element, int byteIndex) {
    int result = element;
    if (byteIndex == MOST_SIGNIFICANT_BYTE_INDEX) {
        result ^= SIGN_BIT_MASK;
    }
    return (result >>> (byteIndex * BITS_PER_BYTE)) & EXTRACT_BYTE_MASK;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.