1
\$\begingroup\$

See the the previous iteration.

Now I refactored the code a bit so that I do not need to pass like 6 parameters to helper methods. Also, I did a small tweak that allows the sort to arrive to the state where the amount of runs is a power of two, which solves the orphan issue: suppose your data has \$1048577 = 2^{20} + 1\$ runs. Now normally you would sort the first \$2^{20}\$ runs, after which you would have to perform another large merge over the entire range in order to merge the last orphan run.

Also, I ignored the generics and pass to my sort any object that implements Comparable. Now, what do you think?

NaturalMergesort.java:

package net.coderodde.util.sorting;

import java.util.Arrays;

/**
 * This class implements natural merge sort for {@code Comparable} objects.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.61 (Oct 1, 2015)
 */
public final class NaturalMergesort {

    private Object[] source;
    private Object[] target;
    private int sourceOffset;
    private int targetOffset;
    private UnsafeIntQueue queue;

    private NaturalMergesort(Object[] array, int fromIndex, int toIndex) {
        if (toIndex - fromIndex < 2) {
            // Nothing to sort.
            return;
        }

        this.queue = buildRunSizeQueue(array, fromIndex, toIndex);
        Object[] buffer = Arrays.copyOfRange(array, fromIndex, toIndex);
        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 {
            // Arrange the stuff such that after the last merge pass all shit is
            // in the argument array.
            source = array;
            target = buffer;
            sourceOffset = fromIndex;
            targetOffset = 0;
        }

        sort();
    }

    private void sort() {    
        // The amount of runs in current merge pass that were not processed yet.
        int runsLeft = queue.size();
        // The amount of elements processed from beginnig of the ranges.
        int offset = 0;

        // While there are runs to merge, do:
        while (queue.size() > 1) {
            if (runsLeft == 3) {
                // We handle this special case in order to get fast to the state
                // where the amount of remaining runs is a power of two. We do 
                // this for the following reason: Suppose you have 1048577 =
                // 1048576 + 1 = 2^(20) + 1 elements in the requested range.
                // Now the algorithm would sort the first 2^(20) element AND
                // will have to do one more merge pass just for putting the last
                // orphan element to its correct position.
                int leftRunLength = queue.dequeue();
                int middleRunLength = queue.dequeue();
                int rightRunLength = queue.dequeue();

                merge(offset,
                      leftRunLength,
                      middleRunLength,
                      rightRunLength);

                queue.enqueue(leftRunLength +
                              middleRunLength + rightRunLength);

                int itmp = sourceOffset;
                sourceOffset = targetOffset;
                targetOffset = itmp;

                Object[] tmp = source;
                source = target;
                target = tmp;

                runsLeft = queue.size();
                offset = 0;
                continue;
            }

            int leftRunLength =  queue.dequeue();
            int rightRunLength = queue.dequeue();

            merge(offset,
                  leftRunLength, 
                  rightRunLength);

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

            if (runsLeft == 0) {
                // Swap array offsets.
                int itmp = sourceOffset;
                sourceOffset = targetOffset;
                targetOffset = itmp;

                // Swap array roles.
                Object[] tmp = source;
                source = target;
                target = tmp;
                // Go to the beginning of the array.
                runsLeft = queue.size();
                offset = 0;
            }
        }
    }

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

    /**
     * Sorts a specific range in the input array.
     * 
     * @param array     the array holding the target range.
     * @param fromIndex the starting, inclusive index of the range to sort.
     * @param toIndex   the ending, exclusive index of the range to sort.
     */
    public static void sort(Object[] array, int fromIndex, int toIndex) {
        new NaturalMergesort(array, fromIndex, toIndex).sort();
    }

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

    /**
     * This method implements a 3-way merge operation.
     * 
     * @param offset          the amount of elements to skip from the beginning
     *                        of the ranges.
     * @param leftRunLength   the length of the left run.
     * @param middleRunLength the length of the middle run.
     * @param rightRunLength  the length of the right run.
     */
    private void merge(int offset,
                       int leftRunLength,
                       int middleRunLength,
                       int rightRunLength) {
        int left = sourceOffset + offset;
        int middle = left + leftRunLength;
        int right = middle + middleRunLength;

        int leftBound = middle;
        int middleBound = right;
        int rightBound = right + rightRunLength;
        int placementOffset = targetOffset + offset;

        while (left < leftBound && middle < middleBound && right < rightBound) {
            Comparable cLeft   = (Comparable) source[left];
            Comparable cMiddle = (Comparable) source[middle];
            Comparable cRight  = (Comparable) source[right];

            if (cRight.compareTo(cMiddle) < 0) {
                // Here, cRight < cMiddle
                if (cRight.compareTo(cLeft) < 0) {
                    target[placementOffset++] = cRight;
                    ++right;
                } else {
                    target[placementOffset++] = cLeft;
                    ++left;
                }
            } else {
                // Here, cMiddle <= cRight.
                if (cLeft.compareTo(cMiddle) <= 0) {
                    target[placementOffset++] = cLeft;
                    ++left;
                } else {
                    target[placementOffset++] = cMiddle;
                    ++middle;
                }
            }
        }

        while (left < leftBound && middle < middleBound) {
            Comparable cLeft   = (Comparable) source[left];
            Comparable cMiddle = (Comparable) source[middle];
            target[placementOffset++] = cMiddle.compareTo(cLeft) < 0 ?
                    source[middle++] :
                    source[left++] ;
        }

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

        while (middle < middleBound && right < rightBound) {
            Comparable cMiddle = (Comparable) source[middle];
            Comparable cRight  = (Comparable) source[right];
            target[placementOffset++] = cMiddle.compareTo(cRight) < 0 ?
                    source[middle++] :
                    source[right++];
        }

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

        System.arraycopy(source, 
                         middle, 
                         target, 
                         placementOffset, 
                         middleBound - middle);

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

    /**
     * This method implements the merging routine.
     * 
     * @param offset         the 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 void merge(int offset,
                       int leftRunLength,
                       int rightRunLength) {
        int left = sourceOffset + offset;
        int right = left + leftRunLength;

        int leftBound = right;
        int rightBound = right + rightRunLength;
        int placementOffset = targetOffset + offset;

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

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

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

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

    /**
     * Scans the runs over the range {@code array[fromIndex .. toIndex - 1]} and 
     * returns a {@link UnsafeIntQueue} containing the sizes of scanned runs in 
     * the same order as they appear in the input range.
     * 
     * @param array     the array containing the desired range.
     * @param fromIndex the starting, inclusive index of the range to scan.
     * @param toIndex   the ending, exclusive index of the range to scan.
     * 
     * @return a {@code UnsafeIntQueue} describing the lengths of the runs in 
     * the input range.
     */
    static UnsafeIntQueue buildRunSizeQueue(Object[] array, 
                                            int fromIndex,
                                            int toIndex) {
        UnsafeIntQueue queue = 
          new UnsafeIntQueue(((toIndex - fromIndex) >>> 1) + 1);

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

        while (left < last) {
            head = left;

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

                queue.enqueue(left - head + 1);
            } else {
                // Scan a strictly descending run.
                while (left < last
                        && ((Comparable) 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 final 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 an integer to the tail of this queue.
         * 
         * @param num the integer to append.
         */
        void enqueue(int num) {
            storage[tail & mask] = num;
            tail = (tail + 1) & mask;
            ++size;
        }

        /**
         * Pops from the head of this queue an integer.
         * 
         * @return the integer 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}.
         */
        private static int fixCapacity(int capacity) {
            capacity = Math.max(capacity, MINIMUM_CAPACITY);
            int ret = 1;

            while (ret < capacity) {
                ret <<= 1;
            }

            return ret;
        }
    }
}

Demo.java:

import java.util.Arrays;
import java.util.Random;
import net.coderodde.util.sorting.NaturalMergesort;

public class Demo {

    private static final int ARRAY_LENGTH = 2000000;
    private static final int FROM_INDEX = 5;
    private static final int TO_INDEX = ARRAY_LENGTH - 6;

    static int getPasses(int runs) {
        return 32 - Integer.numberOfLeadingZeros(runs / 2);
    }

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

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

        System.out.print("My natural merge sort:   ");
        long ta1 = System.currentTimeMillis();
        NaturalMergesort.sort(array2, FROM_INDEX, TO_INDEX);
        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, FROM_INDEX, TO_INDEX);
        long tb2 = System.currentTimeMillis();

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

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

        System.out.println("");

        ////

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

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

        System.out.print("My natural merge sort:   ");
        ta1 = System.currentTimeMillis();
        NaturalMergesort.sort(array2, FROM_INDEX, TO_INDEX);
        tb1 = System.currentTimeMillis();

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

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

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

        System.out.println("Sorted arrays equal: " + 
                Arrays.equals(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;
    }
}
\$\endgroup\$

Your Answer

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

Browse other questions tagged or ask your own question.