3
\$\begingroup\$

(See the previous iteration.)

Now I have optimized my natural merge sort: Suppose the input sequence is

$$\langle 2, 1, 4, 3, 6, 5, \dots, n, n - 1 \rangle.$$

My previous iterations would degrade to \$\Theta(n \log n)\$ on this input. This version will not: After reversing the second run (\$\langle 4, 3 \rangle\$), the algorithm will notice that the first element of the second run is no less than the last element of the first run, and so, it will "merge" these in constant time simply by extending the first run descriptor from \$2\$ to \$4\$, and so on.

Code:

CoderoddeArrays.java:

package net.coderodde.util;

import java.util.Arrays;
import java.util.Comparator;

/**
 * This class contains static methods implementing a natural merge sort
 * algorithm, which runs in time <tt>O(n log m)</tt>, where <tt>n</tt> is the
 * length of the range to sort and <tt>m</tt> is the amount of ascending or 
 * strictly descending contiguous subsequences usually called 'runs' in the
 * input range. The algorithm is stable and the space complexity is 
 * <tt>O(n)</tt>.
 * 
 * @author Rodion Efremov
 * @version 1.61 (Dec 13, 2015)
 */
public class CoderoddeArrays {

    /**
     * Sorts the entire input array. 
     * 
     * @param <T>        the array component type.
     * @param array      the array to sort.
     * @param comparator the value comparator.
     */
    public static final <T> void sort(T[] array, 
                                      Comparator<? super T> comparator) {
        sort(array, 0, array.length, comparator);       
    }

    /**
     * Sorts a specific range in the input array.
     * 
     * @param <T>        the array component type.
     * @param array      the array holding the requested range.
     * @param fromIndex  the least inclusive component index.
     * @param toIndex    the index one past the last inclusive component.
     * @param comparator the value comparator.
     */
    public static final <T> void sort(T[] array, 
                                      int fromIndex, 
                                      int toIndex, 
                                      Comparator<? super T> comparator) {
        if (toIndex - fromIndex < 2) {
            // Trivially sorted or indices are ass-backwards.
            return;
        }

        UnsafeIntQueue queue = buildRunSizeQueue(array, 
                                                 fromIndex, 
                                                 toIndex, 
                                                 comparator);

        T[] buffer = Arrays.copyOfRange(array, fromIndex, toIndex);
        T[] source;
        T[] target;
        int sourceOffset;
        int targetOffset;
        int mergePasses = getPassAmount(queue.size());

        if ((mergePasses & 1) == 1) {
            // Odd amount of passes over the entire range, set the buffer array 
            // as source so that the sorted shit ends up in the original array.
            source = buffer;
            target = array;
            sourceOffset = 0;
            targetOffset = fromIndex;
        } else {
            source = array;
            target = buffer;
            sourceOffset = fromIndex;
            targetOffset = 0;
        }

        // The amount of runs in current merge pass that were not processed yet.
        int runsLeft = queue.size();
        int offset = 0;

        // While there are runs to merge, do:
        while (queue.size() > 1) {
            int leftRunLength =  queue.dequeue();
            int rightRunLength = queue.dequeue();

            merge(source, 
                  target, 
                  sourceOffset + offset, 
                  targetOffset + offset,
                  leftRunLength, 
                  rightRunLength,
                  comparator);

            // Bounce the run we obtained by merging the two runs to the tail.
            queue.enqueue(leftRunLength + rightRunLength);

            runsLeft -= 2;
            offset += leftRunLength + rightRunLength;

            switch (runsLeft) {
                case 1: {
                    int singleLength = queue.dequeue();
                    // In the target array, this 'unmarried' run might be
                    // in the form of two unmerged runs.
                    System.arraycopy(source, 
                                     sourceOffset + offset, 
                                     target, 
                                     targetOffset + offset, 
                                     singleLength);
                    queue.enqueue(singleLength);
                }
                    // FALL THROUGH!

                case 0: {
                    runsLeft = queue.size();
                    offset = 0;

                    T[] tmp = source;
                    source = target;
                    target = tmp;

                    int itmp = sourceOffset;
                    sourceOffset = targetOffset;
                    targetOffset = itmp;
                    break;
                }
            }
        }
    }

    /**
     * Reverses the range <code>array[fromIndex ... toIndex - 1]</code>. Used 
     * for making descending runs ascending.
     * 
     * @param <T> the component type.
     * @param array the array holding the desired range.
     * @param fromIndex the least index of the range to reverse.
     * @param toIndex the index one past the greatest index of the range.
     */
    public static <T> void reverseRun(T[] array, int fromIndex, int toIndex) {
        for(int l = fromIndex, r = toIndex - 1; l < r; ++l, --r) {
            final T tmp = array[l];
            array[l] = array[r];
            array[r] = tmp;
        }
    }

    /**
     * This static class method implements the actual merging routine.
     * 
     * @param <E> the array component type.
     * @param source the source array.
     * @param target the target array.
     * @param offset amount of elements to skip from the beginning of each
     * array.
     * @param leftRunLength the length of the left run.
     * @param rightRunLength the length of the right run.
     */
    private static <T> 
        void merge(T[] source, 
                   T[] target, 
                   int sourceOffset,
                   int targetOffset,
                   int leftRunLength,
                   int rightRunLength,
                   Comparator<? super T> comparator) {
        int left        = sourceOffset;
        int right       = left + leftRunLength;
        int leftBound   = right;
        int rightBound  = right + rightRunLength;
        int targetIndex = targetOffset;

        while (left < leftBound && right < rightBound) {
            target[targetIndex++] = 
                    comparator.compare(source[right], source[left]) < 0 ?
                                       source[right++] : 
                                       source[left++];
        }

        System.arraycopy(source, 
                         left, 
                         target, 
                         targetIndex, 
                         leftBound - left);

        System.arraycopy(source, 
                         right, 
                         target, 
                         targetIndex, 
                         rightBound - right);
    }

    /**
     * This class method returns the amount of merge passes over the input range
     * needed to sort <code>runAmount</code> runs.
     */
    private static int getPassAmount(int runAmount) {
        return 32 - Integer.numberOfLeadingZeros(runAmount - 1);
    }

    /**
     * Scans the runs over the range 
     * <code>array[fromIndex .. toIndex - 1]</code> and returns a 
     * {@link UnsafeIntQueue} containing the sizes of scanned runs in the same
     * order as they appear in the input range.
     * 
     * @param <E> the component type.
     * @param array the array containing the desired range.
     * @param fromIndex the least index of the range to process.
     * @param toIndex the index one past the greatest index contained by the
     * range.
     * 
     * @return a {@link UnsafeIntQueue} describing the lengths of the runs in 
     * the input range.
     */
    static <T> 
        UnsafeIntQueue buildRunSizeQueue(T[] array, 
                                         int fromIndex,
                                         int toIndex,
                                         Comparator<? super T> comparator) {
        UnsafeIntQueue queue = 
          new UnsafeIntQueue(((toIndex - fromIndex) >>> 1) + 1);

        int head;
        int left = fromIndex;
        int right = left + 1;
        int last = toIndex - 1;
        boolean previousRunWasDescending = false;

        while (left < last) {
            head = left;

            // Decide the direction of the next run.
            if (comparator.compare(array[left++], array[right++]) <= 0) {
                // Scan an ascending run.
                while (left < last
                        && comparator.compare(array[left], array[right]) <= 0) {
                    ++left;
                    ++right;
                }

                int runLength = left - head + 1;

                if (previousRunWasDescending) {
                    if (comparator.compare(array[head - 1], array[head]) <= 0) {
                        // "Merge" the current run to the previous one in 
                        // constant time.
                        queue.addToLast(runLength);
                    } else {
                        queue.enqueue(runLength);
                    }
                } else {
                    queue.enqueue(runLength);
                }

                previousRunWasDescending = false;
            } else {
                // Scan a strictly descending run.
                while (left < last
                        && comparator.compare(array[left], array[right]) > 0) {
                    ++left;
                    ++right;
                }

                int runLength = left - head + 1;
                reverseRun(array, head, right);

                if (previousRunWasDescending) {
                    if (comparator.compare(array[head - 1], array[head]) <= 0) {
                        // Merge the current run with the previous one.
                        queue.addToLast(runLength);
                    } else {
                        queue.enqueue(runLength);
                    }
                } else {
                    queue.enqueue(runLength);
                }

                previousRunWasDescending = true;
            }

            ++left;
            ++right;
        }

        // A special case: the very last element may be left without buddies
        // so make it (the only) 1-element run. Merge it to the previous run if
        // possible.
        if (left == last) {
            if (comparator.compare(array[last - 1], array[last]) <= 0) {
                queue.addToLast(1);
            } else {
                queue.enqueue(1);
            }
        }

        return queue;
    }

    /**
     * This is the implementation class for an array-based queue of integers. It 
     * sacrifices under- and overflow checks as to squeeze a little bit more of
     * efficiency and thus is an ad-hoc data structure hidden from the client
     * programmers.
     * 
     * @author Rodion Efremov
     * @version 2014.12.01
     */
    private static class UnsafeIntQueue {

        /**
         * The minimum capacity of this queue.
         */
        private static final int MINIMUM_CAPACITY = 256;

        /**
         * Stores the actual elements.
         */
        private final int[] storage;

        /**
         * Points to the element that will be dequeued next.
         */
        private int head;

        /**
         * Points to the array component to which the next element will be 
         * inserted.
         */
        private int tail;

        /**
         * Caches the amount of elements stored.
         */
        private int size;

        /**
         * Used for faster head/tail updates.
         */
        private final int mask;

        int counter = 0;

        /**
         * Creates an empty integer queue with capacity of the least power of
         * two no less than original capacity value.
         */
        UnsafeIntQueue(int capacity) {
            capacity = fixCapacity(capacity);
            this.mask = capacity - 1;
            this.storage = new int[capacity];
        }

        /**
         * Appends a run size to the tail of this queue.
         * 
         * @param runSize the run size to append.
         */
        void enqueue(int runSize) {
            storage[tail] = runSize;
            tail = (tail + 1) & mask;
            ++size;
        }

        void addToLast(int runSize) {
            counter++;
            storage[(tail - 1) & mask] += runSize;
        }

        /**
         * Pops from the head of this queue a run size.
         * 
         * @return the run size at the head of this queue.
         */
        int dequeue() {
            int ret = storage[head];
            head = (head + 1) & mask;
            --size;
            return ret;
        }

        /**
         * Returns the amount of values stored in this queue.
         */
        int size() {
            return size;
        }

        /**
         * This routine is responsible for computing an integer that is a power
         * of two no less than <code>capacity</code>.
         */
        private static int fixCapacity(int capacity) {
            if (capacity < MINIMUM_CAPACITY) {
                return MINIMUM_CAPACITY;
            }

            int ret = Integer.highestOneBit(capacity);
            return ret != capacity ? ret <<= 1 : ret;
        }
    }
}

Demo.java:

package net.coderodde.util;

import java.util.Random;

public class Demo {

    private static final int N = 1_000_000;

    public static void main(String[] args) {        
        final long seed = System.currentTimeMillis();
        System.out.println("Seed: " + seed);

        //// RANDOM DATA DEMO ////
        System.out.println("-- Random data demo --");

        Random rnd = new Random(seed);
        Integer[] array1 = getRandomIntegerArray(N, -10000, 10000, rnd);
        Integer[] array2 = array1.clone();
        Integer[] array3 = array1.clone();

        System.out.print("My natural merge sort:   ");
        long startTime = System.nanoTime();
        net.coderodde.util.CoderoddeArrays.sort(array1, 
                                                10, 
                                                array1.length - 10,
                                                Integer::compare);
        long endTime = System.nanoTime();
        System.out.printf("%.3f milliseconds.\n", 
                          1.0 * (endTime - startTime) / 1e6);

        System.out.print("java.util.Arrays.sort(): ");
        startTime = System.nanoTime();
        java.util.Arrays.sort(array2, 
                              10, 
                              array2.length - 10,
                              Integer::compare);
        endTime = System.nanoTime();
        System.out.printf("%.3f milliseconds.\n", 
                          1.0 * (endTime - startTime) / 1e6);

        System.out.print("java.util.Arrays.parallelSort(): ");
        startTime = System.nanoTime();
        java.util.Arrays.parallelSort(array3, 
                                      10, 
                                      array3.length - 10,
                                      Integer::compare);
        endTime = System.nanoTime();
        System.out.printf("%.3f milliseconds.\n", 
                          1.0 * (endTime - startTime) / 1e6);

        // weak version as parallelSort seems to sort unstably.
        System.out.println("Sorted arrays equal: " + strongEquals(array1, 
                                                                  array2));

        System.out.println("");

        ////
        ////

        System.out.println("-- Presorted data demo --");

        array1 = getPresortedIntegerArray(N);
        array2 = array1.clone();
        array3 = array1.clone();

        System.out.print("My natural merge sort:   ");
        startTime = System.nanoTime();
        net.coderodde.util.CoderoddeArrays.sort(array1, 
                                                10, 
                                                array1.length - 10,
                                                Integer::compare);
        endTime = System.nanoTime();
        System.out.printf("%.3f milliseconds.\n", 
                          1.0 * (endTime - startTime) / 1e6);

        System.out.print("java.util.Arrays.sort(): ");
        startTime = System.nanoTime();
        java.util.Arrays.sort(array2, 
                              10, 
                              array2.length - 10,
                              Integer::compare);
        endTime = System.nanoTime();
        System.out.printf("%.3f milliseconds.\n", 
                          1.0 * (endTime - startTime) / 1e6);

        System.out.print("java.util.Arrays.parallelSort(): ");
        startTime = System.nanoTime();
        java.util.Arrays.parallelSort(array3, 
                                      10, 
                                      array3.length - 10,
                                      Integer::compare);
        endTime = System.nanoTime();
        System.out.printf("%.3f milliseconds.\n", 
                          1.0 * (endTime - startTime) / 1e6);

        // weak version as parallelSort seems to sort unstably.
        System.out.println("Sorted arrays equal: " + strongEquals(array1, 
                                                                  array2));

        System.out.println("");

        ////
        ////

        System.out.println("-- Bad data demo --");

        array1 = getBadIntegerArray(N);
        array2 = array1.clone();
        array3 = array1.clone();

        System.out.print("My natural merge sort:   ");
        startTime = System.nanoTime();
        net.coderodde.util.CoderoddeArrays.sort(array1, 
                                                10, 
                                                array1.length - 10,
                                                Integer::compare);
        endTime = System.nanoTime();
        System.out.printf("%.3f milliseconds.\n", 
                          1.0 * (endTime - startTime) / 1e6);

        System.out.print("java.util.Arrays.sort(): ");
        startTime = System.nanoTime();
        java.util.Arrays.sort(array2, 
                              10, 
                              array2.length - 10,
                              Integer::compare);
        endTime = System.nanoTime();
        System.out.printf("%.3f milliseconds.\n", 
                          1.0 * (endTime - startTime) / 1e6);

        System.out.print("java.util.Arrays.parallelSort(): ");
        startTime = System.nanoTime();
        java.util.Arrays.parallelSort(array3, 
                                      10, 
                                      array3.length - 10,
                                      Integer::compare);
        endTime = System.nanoTime();
        System.out.printf("%.3f milliseconds.\n", 
                          1.0 * (endTime - startTime) / 1e6);

        // weak version as parallelSort seems to sort unstably.
        System.out.println("Sorted arrays equal: " + strongEquals(array1, 
                                                                  array2));
        System.out.println();

        ////
        ////

        System.out.println("-- Unbalanced data demo --");

        array1 = getUnbalancedRunArray(N, rnd);
        array2 = array1.clone();
        array3 = array1.clone();

        System.out.print("My natural merge sort:   ");
        startTime = System.nanoTime();
        net.coderodde.util.CoderoddeArrays.sort(array1, 
                                                10, 
                                                array1.length - 10,
                                                Integer::compare);
        endTime = System.nanoTime();
        System.out.printf("%.3f milliseconds.\n", 
                          1.0 * (endTime - startTime) / 1e6);

        System.out.print("java.util.Arrays.sort(): ");
        startTime = System.nanoTime();
        java.util.Arrays.sort(array2, 
                              10, 
                              array2.length - 10,
                              Integer::compare);
        endTime = System.nanoTime();
        System.out.printf("%.3f milliseconds.\n", 
                          1.0 * (endTime - startTime) / 1e6);

        System.out.print("java.util.Arrays.parallelSort(): ");
        startTime = System.nanoTime();
        java.util.Arrays.parallelSort(array3, 
                                      10, 
                                      array3.length - 10,
                                      Integer::compare);
        endTime = System.nanoTime();
        System.out.printf("%.3f milliseconds.\n", 
                          1.0 * (endTime - startTime) / 1e6);

        // weak version as parallelSort seems to sort unstably.
        System.out.println("Sorted arrays equal: " + strongEquals(array1, 
                                                                  array2));
    }

    /**
     * This method checks whether the all input arrays are of identical lengths
     * and content.
     * 
     * @param <T>    the array component type.
     * @param arrays the array of arrays to check.
     * @return {@code true} only if all input arrays are identical.
     */
    public static <T> boolean strongEquals(T[]... arrays) {
        if (arrays.length == 0) {
            return true;
        }

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

        int numElements = arrays[0].length;
        int numArrays = arrays.length;

        for (int elementIndex = 0; elementIndex < numElements; ++elementIndex) {
            for (int arrayIndex = 0; arrayIndex < numArrays - 1; ++arrayIndex) {
                if (arrays[arrayIndex][elementIndex] 
                        != arrays[arrayIndex + 1][elementIndex]) {
                    return false;
                }
            }
        }

        return true;
    }

    private static Integer[] getRandomIntegerArray(int size, 
                                                   int min,
                                                   int max,
                                                   Random rnd) {
        Integer[] array = new Integer[size];

        for (int i = 0; i < size; ++i) {
            array[i] = rnd.nextInt(max - min + 1) + min;
        }

        return array;
    }

    private static Integer[] getUnbalancedRunArray(int size, Random rnd) {
        Integer[] array = new Integer[size];
        int index = 0;

        while (index < size) {
            int runLength = Math.min(size - index, rnd.nextInt(10000));
            int start = rnd.nextInt();

            for (int i = 0; i < runLength; ++i, ++index) {
                array[index] = start - i;
            }
        }

        return array;
    }

    private static Integer[] getPresortedIntegerArray(int size) {
        Integer[] array = new Integer[size];

        for (int i = 0; i < size; ++i) {
            array[i] = i % (size / 8);
        }

        for (int i = 0, j = size - 1; i < j; ++i, --j) {
            Integer tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }

        return array;
    }

    // This checks that my natural merge sort can handle the following input:
    // 4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9, ...
    // The above sequence would imply many merge passes, yet after reversing 
    // them we do not need to merge anything.
    private static Integer[] getBadIntegerArray(int size) {
        Integer[] array = new Integer[size];

        for (int i = 0; i < size; ++i) {
            array[i] = i;
        }

        for (int i = 0; i < size / 100 + 1; ++i) {
           CoderoddeArrays.reverseRun(array, 
                                      10000 * i, 
                                      Math.min(size, 100 * (i + 1)));
        }

        return array;
    }
}

The performance figures are as follows:

Seed: 1450008290459
-- Random data demo --
My natural merge sort: 1009.111 milliseconds.
java.util.Arrays.sort(): 1310.094 milliseconds.
java.util.Arrays.parallelSort(): 873.579 milliseconds.
Sorted arrays equal: true

-- Presorted data demo --
My natural merge sort: 193.198 milliseconds.
java.util.Arrays.sort(): 216.217 milliseconds.
java.util.Arrays.parallelSort(): 439.445 milliseconds.
Sorted arrays equal: true

-- Bad data demo --
My natural merge sort: 43.975 milliseconds.
java.util.Arrays.sort(): 70.619 milliseconds.
java.util.Arrays.parallelSort(): 123.902 milliseconds.
Sorted arrays equal: true

-- Unbalanced data demo --
My natural merge sort: 191.461 milliseconds.
java.util.Arrays.sort(): 24.831 milliseconds.
java.util.Arrays.parallelSort(): 95.397 milliseconds.
Sorted arrays equal: true

Anything I could improve? Naming conventions? Coding style? Performance?

\$\endgroup\$
2
\$\begingroup\$
            if (previousRunWasDescending) {
                if (comparator.compare(array[head - 1], array[head]) <= 0) {
                    // Merge the current run with the previous one.
                    queue.addToLast(runLength);
                } else {
                    queue.enqueue(runLength);
                }
            } else {
                queue.enqueue(runLength);
            }

This section of code is duplicated. I think you could extract it into a separate function, as well as merging the two conditions:

            if (previousRunWasDescending && comparator.compare(array[head - 1], array[head]) <= 0) {
                // Merge the current run with the previous one.
                queue.addToLast(runLength);
            } else {
                queue.enqueue(runLength);
            }
\$\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.