2
\$\begingroup\$

See the previous iteration: Natural merge sort in Java

See the next iteration: Natural merge sort in Java - follow-up 2

Arrays.java

package net.coderodde.util;

/**
 * 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.
 * 
 * @author Rodion Efremov
 * @version 2014.12.01
 */
public class Arrays {

    /**
     * Sorts the entire input array. 
     */
    public static final <E extends Comparable<? super E>>
        void sort(final E[] array) {
        sort(array, 0, array.length);       
    }

    /**
     * Sorts a specific range in the input array.
     */
    public static final <E extends Comparable<? super E>> 
        void sort(final E[] array, final int fromIndex, final int toIndex) {
        if (toIndex - fromIndex < 2) {
            // Trivially sorted or indices are ass-backwards.
            return;
        }

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

        final E[] buffer = array.clone();
        final int mergePasses = getPassAmount(queue.size());

        E[] source;
        E[] target;

        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;
        } else {
            source = array;
            target = buffer;
        }

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

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

            merge(source, 
                  target, 
                  offset, 
                  leftRunLength, 
                  rightRunLength);

            // 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:
                    final int singleLength = queue.dequeue();
                    // In the target array, this 'unmarried' run might be
                    // in the form of two unmerged runs.
                    System.arraycopy(source, 
                                     offset, 
                                     target, 
                                     offset, 
                                     singleLength);
                    queue.enqueue(singleLength);

                    // FALL THROUGH!

                case 0:
                    runsLeft = queue.size();
                    offset = fromIndex;
                    final E[] tmp = source;
                    source = target;
                    target = tmp;
                    break;
            }
        }
    }

    /**
     * Reverses the range <code>array[fromIndex ... toIndex - 1]</code>. Used 
     * for making descending runs ascending.
     * 
     * @param <E> 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 <E> void reverseRun(final E[] array, 
                                      final int fromIndex,
                                      final int toIndex) {
        for(int l = fromIndex, r = toIndex - 1; l < r; ++l, --r) {
            final E tmp = array[l];
            array[l] = array[r];
            array[r] = tmp;
        }
    }

    /**
     * Checks whether all given arrays are of the same length and has identical
     * references at every corresponding array components.
     */
    public static final <E> boolean arraysEqual(final E[]... arrays) {
        if (arrays.length < 2) {
            return true;
        }

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

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

        return true;
    }

    /**
     * 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 <E extends Comparable<? super E>> 
        void merge(final E[] source, 
                   final E[] target, 
                   int offset,
                   int leftRunLength,
                   int rightRunLength) {
        int left = offset;
        int right = left + leftRunLength;

        final int leftBound = right;
        final int rightBound = right + rightRunLength;

        while (left < leftBound && right < rightBound) {
            target[offset++] = source[right].compareTo(source[left]) < 0 ? 
                               source[right++] :
                               source[left++];
        }

        // Either 'left < leftBound' or 'right < rightBound', not both.
        if (left < leftBound) {
            System.arraycopy(source, left, target, offset, leftBound - left);
        } else if (right < rightBound) {
            System.arraycopy(source, right, target, offset, 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) {
        int setBitCount = 0;
        int mostSignificantBitIndex = -1;
        int mask = 0x40000000;

        loop:
        for (int i = 30; i >= 0; --i, mask >>= 1) {
            if ((runAmount & mask) != 0) {
                ++setBitCount;

                switch (setBitCount) {
                    case 1:
                        mostSignificantBitIndex = i;
                        break;

                    case 2:
                        break loop;
                }
            }
        }

        if (setBitCount > 1) {
            // Once here, 'runAmount' is not a power of two; make it one.
            runAmount = (1 << (mostSignificantBitIndex + 1));
        }

        int ret = 0;

        while ((runAmount & 1) == 0) {
            ++ret;
            runAmount >>= 1;
        }

        return ret;
    }

    /**
     * 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 <E extends Comparable<? super E>> 
        UnsafeIntQueue buildRunSizeQueue(final E[] array, 
                                         final int fromIndex,
                                         final int toIndex) {
        final UnsafeIntQueue queue = 
          new UnsafeIntQueue(((toIndex - fromIndex) >>> 1) + 1);

        int head;
        int left = fromIndex;
        int right = left + 1;
        final int last = toIndex - 1;

        while (left < last) {
            head = left;

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

                queue.enqueue(left - head + 1);
            } else {
                // Scan a strictly descending run.
                while (left < last
                        && array[left].compareTo(array[right]) > 0)  {
                    ++left;
                    ++right;
                }

                queue.enqueue(left - head + 1);
                // We reverse a strictly descending run as to minimize the
                // the amount of runs scanned in total. Strictness is required.
                reverseRun(array, head, right);
            }

            ++left;
            ++right;
        }

        // A special case: the very last element may be left without buddies
        // so make it (the only) 1-element run.
        if (left == last) {
            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;

        /**
         * 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 & mask] = runSize;
            tail = (tail + 1) & mask;
            ++size;
        }

        /**
         * 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) {
                capacity = MINIMUM_CAPACITY;
            }

            int mask = 0x40000000;
            int totalSetBits = 0;
            int mostSignificantBitIndex = -1;

            loop:
            for (int i = 30; i >= 0; mask >>= 1, --i) {
                if ((capacity & mask) != 0) {
                    ++totalSetBits;

                    switch (totalSetBits) {
                        case 1:
                            mostSignificantBitIndex = i;
                            break;

                        case 2:
                            break loop;
                    }
                }
            }

            if (totalSetBits > 1) {
                // Make capacity a power of two that is no less than
                // input capacity
                capacity = (1 << (mostSignificantBitIndex + 1));
            }

            // Here, capacity is a power of two.
            return capacity;
        }
    }
}

Demo.java

package net.coderodde.util;

import java.util.Random;

public class Demo {

    private static final int N = 2000000;

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

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

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

        System.out.print("My natural merge sort:   ");
        long ta1 = System.currentTimeMillis();
        net.coderodde.util.Arrays.sort(array2);
        long tb1 = System.currentTimeMillis();

        System.out.println((tb1 - ta1) + " ms.");

        System.out.print("java.util.Arrays.sort(): ");
        long ta2 = System.currentTimeMillis();
        java.util.Arrays.sort(array1);
        long tb2 = System.currentTimeMillis();

        System.out.println((tb2 - ta2) + " ms.");

        System.out.println("Sorted arrays equal: " + 
                Arrays.arraysEqual(array1, array2));

        System.out.println("");

        ////

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

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

        System.out.print("My natural merge sort:   ");
        ta1 = System.currentTimeMillis();
        net.coderodde.util.Arrays.sort(array2);
        tb1 = System.currentTimeMillis();

        System.out.println((tb1 - ta1) + " ms.");

        System.out.print("java.util.Arrays.sort(): ");
        ta2 = System.currentTimeMillis();
        java.util.Arrays.sort(array1);
        tb2 = System.currentTimeMillis();

        System.out.println((tb2 - ta2) + " ms.");

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

    private static Integer[] getRandomIntegerArray(final int size, 
                                                   final int min,
                                                   final int max,
                                                   final Random rnd) {
        final 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[] getPresortedIntegerArray(final int size) {
        final 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) {
            final Integer tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }

        return array;
    }
}
  • RunSizeDeque

    • Renamed to UnsafeIntQueue as to reflect the fact that it is a queue of primitive integers, and that the structure does not check for under-/overflow for efficiency.
    • Hidden from client programmer as a static private inner class of net.coderodde.util.Arrays.
    • Avoids using stuff from java.lang.Math to compute a capacity that is a power of 2.
    • The user of UnsafeIntQueue, i.e. the sort method, will do everything needed to avoid under-/overflow.
  • RunCounter

    • Moved to net.coderodde.util.Arrays in the form of a private static method.
    • I disagree about the need to encapsulate run scanning logic into a subroutine, and that's why:
      1. It's only a loop with a body containing two simple updates.
      2. As it will be called in the worst case O(n) times, and calls in general are expensive, it will introduce an efficiency penalty which I want to avoid.
      3. And, no. The code will not be any more readable.
    • reverseRun renamed to reverse and made public as it implements an "important algorithm."
  • sort
    • Eliminates the need for java.lang.Math-stuff.
    • What comes to efficiency, just run the demo and you'll see.
    • If the input array has length, say, n = 2k, and is of form $$\langle 1, 2, \dots, k, k, k - 1, \dots, 2, 1 \rangle,$$ natural merge sort will do one pass over the array just to find out that it consists of two runs, the second of which is reversed, reverse it, and do a single merge over the array to merge the two. That's it! 2 and a half passes over the range instead of $$\log 2k = \log k + 1.$$
\$\endgroup\$
2
\$\begingroup\$

There's a different trick you can use for getPassAmount .... the solution I would use is:

private static final int getPassCount(int size) {
    return 32 - Integer.numberOfLeadingZeros(size - 1);
}

Note the use of the Integer.numberOfLeadingZeros. The trick here is to do the boundary-condition logic right, requiring the size-1 and the guard-conditions to check for a size-1 list...

\$\endgroup\$
  • \$\begingroup\$ No. The least value of size ever passed to getPassCount is 1, so that eliminates infinite looping. And on size = 1, zero is exactly what I want it to return as you need no merge passes over the range containing one run. \$\endgroup\$ – coderodde Dec 3 '14 at 16:55
  • \$\begingroup\$ @coderodde - updated the answer based on your comment. \$\endgroup\$ – rolfl Dec 3 '14 at 16:58

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.