3
\$\begingroup\$

(See the next iteration.)

This natural merge sort here is from "Sublinear Merging and Natural Mergesort" by Svante Carlsson, Christos Levcopoulos and Ola Petersson. The funky part is that it may merge two sorted runs in sublinear time on some instances. Here it goes:

AdaptiveMergesort.java

package net.coderodde.util;

import java.util.Arrays;
import java.util.Objects;

public final class AdaptiveMergesort {

    private AdaptiveMergesort() {}

    public static <T extends Comparable<? super T>> void sort(T[] array) {
        Objects.requireNonNull(array, "The input array is null.");
        sort(array, 0, array.length);
    }

    public static <T extends Comparable<? super T>> void sort(T[] array,
                                                              int fromIndex,
                                                              int toIndex) {
        Objects.requireNonNull(array, "The input array is null.");
        checkIndices(array.length, fromIndex, toIndex);

        int rangeLength = toIndex - fromIndex;

        if (rangeLength < 2) {
            return; // Trivially sorted.
        }

        T[] aux = Arrays.copyOfRange(array, fromIndex, toIndex);
        RunQueue queue = new RunLengthQueueBuilder<>(aux).run();
        int runsLeft = queue.size();

        while (queue.size() > 1) {
            switch (runsLeft) {
                case 1:
                    // Bounce the lonely leftover run back to the tail of the 
                    // queue:
                    queue.enqueue(queue.dequeue());
                    // Fall through!

                case 0:
                    runsLeft = queue.size();
                    continue;
            }

            Run run1 = queue.dequeue();
            Run run2 = queue.dequeue();
            queue.enqueue(merge(aux, run1, run2));
        }

        int arrayIndex = fromIndex;

        for (Interval interval = queue.dequeue().first; 
                interval != null; 
                interval = interval.next) {
            for (int i = interval.from; i <= interval.to; ++i) {
                array[arrayIndex++] = aux[i];
            }
        }
    }

    private static <T extends Comparable<? super T>> Run merge(T[] aux,
                                                               Run run1, 
                                                               Run run2) {
        Interval headInterval1 = run1.first;
        Interval headInterval2 = run2.first;
        Interval mergedRunHead = null;
        Interval mergedRunTail = null;

        while (headInterval1 != null && headInterval2 != null) {
            T head1 = aux[headInterval1.from];
            T head2 = aux[headInterval2.from];

            if (head1.compareTo(head2) <= 0) {
                T tail1 = aux[headInterval1.to];

                if (tail1.compareTo(head2) <= 0) {
                    if (mergedRunHead == null) {
                        mergedRunHead = headInterval1;
                        mergedRunTail = headInterval1;
                    } else {
                        mergedRunTail.next = headInterval1;
                        headInterval1.prev = mergedRunTail;
                        mergedRunTail = headInterval1;
                    }

                    headInterval1 = headInterval1.next;
                    continue;
                }

                int index = findUpperBound(aux,
                                           headInterval1.from,
                                           headInterval1.to + 1,
                                           head2);

                Interval newInterval = new Interval(headInterval1.from, index - 1);
                headInterval1.from = index;

                if (mergedRunHead == null) {
                    mergedRunHead = newInterval;
                    mergedRunTail = newInterval;
                } else {
                    mergedRunTail.next = newInterval;
                    newInterval.prev = mergedRunTail;
                    mergedRunTail = newInterval;
                }
            } else {
                T tail2 = aux[headInterval2.to];

                if (tail2.compareTo(head1) < 0) {
                    if (mergedRunHead == null) {
                        mergedRunHead = headInterval2;
                        mergedRunTail = headInterval2;
                    } else {
                        mergedRunTail.next = headInterval2;
                        headInterval2.prev = mergedRunTail;
                        mergedRunTail = headInterval2;
                    }

                    headInterval2 = headInterval2.next;
                    continue;
                }

                int index = findLowerBound(aux, 
                                           headInterval2.from,
                                           headInterval2.to + 1,
                                           head1);

                Interval newInterval = new Interval(headInterval2.from,
                                                    index - 1);
                headInterval2.from = index; 

                if (mergedRunHead == null) {
                    mergedRunHead = newInterval;
                    mergedRunTail = newInterval;
                } else {
                    mergedRunTail.next = newInterval;
                    newInterval.prev = mergedRunTail;
                    mergedRunTail = newInterval;
                }
            }
        }

        // Append the leftover intervals of a currently non-empty run to the
        // tail of the merged run:
        if (headInterval1 != null) {
            mergedRunTail.next = headInterval1;
            headInterval1.prev = mergedRunTail;
            mergedRunTail = headInterval1;
        } else {
            mergedRunTail.next = headInterval2;
            headInterval2.prev = mergedRunTail;
            mergedRunTail = headInterval2;
        }

        // Reuse 'run1' in order not to abuse the heap memory:
        run1.first = mergedRunHead;
        run1.last = mergedRunTail;
        return run1;
    }

    private static void checkIndices(int arrayLength, 
                                     int fromIndex, 
                                     int toIndex) {
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException(
                    "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }

        if (fromIndex < 0) {
            throw new ArrayIndexOutOfBoundsException(
                    "fromIndex = " + fromIndex);
        }

        if (toIndex > arrayLength) {
            throw new ArrayIndexOutOfBoundsException(
                    "toIndex = " + toIndex);
        }
    }

    private static final class Interval {
        int from;
        int to;
        Interval prev;
        Interval next;

        Interval(int from, int to) {
            this.from = from;
            this.to = to;
        }

        @Override
        public String toString() {
            return "(" + from + ", " + to + ")";
        }
    }

    private static final class Run {
        Interval first;
        Interval last;

        Run(int from, int to) {
            first = new Interval(from, to);
            last = first;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder("[");
            String separator = "";

            for (Interval interval = first; 
                    interval != null; 
                    interval = interval.next) {
                sb.append(separator).append(interval);
                separator = ", ";
            }

            return sb.append("]").toString();
        }
    }

    private static final class RunQueue {

        private final Run[] runArray;
        private final int mask;
        private int head;
        private int tail;
        private int size;

        RunQueue(int capacity) {
            capacity = ceilCapacityToPowerOfTwo(capacity);
            this.mask = capacity - 1;
            this.runArray = new Run[capacity];
        }

        void enqueue(Run run) {
            runArray[tail] = run;
            tail = (tail + 1) & mask;
            ++size;
        }

        void addToLastRun(int runLength) {
            runArray[(tail - 1) & mask].first.to += runLength;
        }

        Run dequeue() {
            Run run = runArray[head];
            head = (head + 1) & mask;
            --size;
            return run;
        }

        int size() {
            return size;
        }

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

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder("[");
            String separator = "";

            for (int i = 0; i < size; ++i) {
                sb.append(separator).append(runArray[(head + i) & mask]);
                separator = ", ";
            }

            return sb.append("]").toString();
        }
    }

    private static final class 
            RunLengthQueueBuilder<T extends Comparable<? super T>> {

        private final RunQueue queue;
        private final T[] array;
        private int head;
        private int left;
        private int right;
        private final int last;
        private boolean previousRunWasDesending;

        RunLengthQueueBuilder(T[] array) {
            this.queue = new RunQueue((array.length >>> 1) + 1);
            this.array = array;
            this.left  = 0;
            this.right = 1;
            this.last  = array.length - 1;
        }

        RunQueue run() {
            while (left < last) {
                head = left;

                if (array[left++].compareTo(array[right++]) <= 0) {
                    scanAscendingRun();
                } else {
                    scanDescendingRun();
                }

                ++left;
                ++right;
            }

            if (left == last) {
                if (array[last - 1].compareTo(array[last]) <= 0) {
                    queue.addToLastRun(1);
                } else {
                    queue.enqueue(new Run(left, left));
                }
            }

            return queue;
        }

        void scanAscendingRun() {
            while (left < last && array[left].compareTo(array[right]) <= 0) {
                ++left;
                ++right;
            }

            Run run = new Run(head, left);

            if (previousRunWasDesending) {
                if (array[head - 1].compareTo(array[head]) <= 0) {
                    queue.addToLastRun(right - head);
                } else {
                    queue.enqueue(run);
                }
            } else {
                queue.enqueue(run);
            }

            previousRunWasDesending = false;
        }

        void scanDescendingRun() {
            while (left < last && array[left].compareTo(array[right]) > 0) {
                ++left;
                ++right;
            }

            Run run = new Run(head, left);
            reverseRun(array, head, left);

            if (previousRunWasDesending) {
                if (array[head - 1].compareTo(array[head]) <= 0) {
                    queue.addToLastRun(right - head);
                } else {
                    queue.enqueue(run);
                }
            } else {
                queue.enqueue(run);
            }

            previousRunWasDesending = true;
        }

        private void reverseRun(T[] array, int i, int j) {
            for (; i < j; ++i, --j) {
                T tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
    }

    private static <T extends Comparable<? super T>> 
        int lowerBound(T[] array, int fromIndex, int toIndex, T value) {
        int count = toIndex - fromIndex;
        int it;

        while (count > 0) {
            it = fromIndex;
            int step = count >>> 1;
            it += step;

            if (array[it].compareTo(value) < 0) {
                fromIndex = ++it;
                count -= step + 1;
            } else {
                count = step;
            }
        }

        return fromIndex;
    }

    private static <T extends Comparable<? super T>>
        int upperBound(T[] array, int fromIndex, int toIndex, T value) {
        int count = toIndex - fromIndex;
        int it;

        while (count > 0) {
            it = fromIndex; 
            int step = count >>> 1;
            it += step;

            if (array[it].compareTo(value) <= 0) {
                fromIndex = ++it;
                count -= step + 1;
            } else {
                count = step;
            }
        }

        return fromIndex;
    }

    private static <T extends Comparable<? super T>> 
        int findLowerBound(T[] array, int fromIndex, int toIndex, T value) {
        int bound = 1;
        int rangeLength = toIndex - fromIndex;

        while (bound < rangeLength &&
                array[bound + fromIndex].compareTo(value) < 0) {
            bound <<= 1;
        }

        return lowerBound(array, 
                          fromIndex + (bound >>> 1), 
                          Math.min(toIndex, fromIndex + bound), 
                          value);
    }

    private static <T extends Comparable<? super T>> 
        int findUpperBound(T[] array, int fromIndex, int toIndex, T value) {
        int bound = 1;
        int rangeLength = toIndex - fromIndex;

        while (bound < rangeLength 
                && array[bound + fromIndex].compareTo(value) < 0) {
            bound <<= 1;
        }

        return upperBound(array, 
                          fromIndex + (bound >>> 1), 
                          Math.min(toIndex, fromIndex + bound),
                          value);
    }
}

Demo.java

package net.coderodde.util;

import java.util.Arrays;
import java.util.Random;

public final class Demo {

    private static final int FROM_INDEX = 7;
    private static final int SKIP_RIGHT = 9;
    private static final int ARRAY_LENGTH = 50_000;
    private static final int BLOCKS = 1000;
    private static final int MIN_ELEMENT = -10_000;
    private static final int MAX_ELEMENT = 10_000;
    private static final int MAX_RUN_LENGTH = 100;
    private static final int RUNS = 1000;

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

        warmup(random);
        benchmark(random);
    }

    private static void warmup(Random random) {
        System.out.println("Warming up...");

        Integer[] array = getBlockedArray(ARRAY_LENGTH, BLOCKS, random);
        warmup(array);

        array = getRandomArray(ARRAY_LENGTH, random);
        warmup(array);

        array = getFunnyArray(ARRAY_LENGTH, random);
        warmup(array);

        array = getRunnyArray(ARRAY_LENGTH, RUNS, random);
        warmup(array);

        System.out.println("Warming up done!\n\n");
    }

    private static void benchmark(Random random) {
        Integer[] array = getBlockedArray(ARRAY_LENGTH, BLOCKS, random);
        System.out.println("--- Blocked array ---");
        benchmark(array);

        array = getRandomArray(ARRAY_LENGTH, random);
        System.out.println("--- Random array ----");
        benchmark(array);

        array = getFunnyArray(ARRAY_LENGTH, random);
        System.out.println("--- Funny array -----");
        benchmark(array);

        array = getRunnyArray(ARRAY_LENGTH, RUNS, random);
        System.out.println("--- Runny array -----");
        benchmark(array);
    }

    private static void warmup(Integer[] array1) {
        perform(false, array1);
    }

    private static void benchmark(Integer[] array1) {
        perform(true, array1);
    }

    private static void perform(boolean output, 
                                Integer[] array1) {
        Integer[] array2 = array1.clone();
        int length = array1.length;

        long startTime = System.currentTimeMillis();
        Arrays.sort(array1, FROM_INDEX, length - SKIP_RIGHT);
        long endTime = System.currentTimeMillis();

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

        startTime = System.currentTimeMillis();
        AdaptiveMergesort.sort(array2, FROM_INDEX, length - SKIP_RIGHT);
        endTime = System.currentTimeMillis();

        if (output) {
            System.out.println("AdaptiveMergesort.sort in " + 
                               (endTime - startTime) +
                               " milliseconds.");

            System.out.println("Algorithms agree: " +
                               Arrays.equals(array1, array2));
        }
    }

    private static final Integer[] getBlockedArray(int length, 
                                                   int blocks,
                                                   Random random) {
        Integer[] array = getAscendingArray(length);
        blockify(array, blocks, random);
        return array;
    }

    private static final Integer[] getRandomArray(int length, Random random) {
        Integer[] array = new Integer[length];

        for (int i = 0; i < length; ++i) {
            array[i] = random.nextInt(MAX_ELEMENT - MIN_ELEMENT + 1) + MIN_ELEMENT;
        }

        return array;
    }

    private static final Integer[] getFunnyArray(int length, Random random) {
        Integer[] array = new Integer[length];

        int index = 0;

        while (index < array.length) {
            int remaining = array.length - index;
            int next = random.nextInt(MAX_RUN_LENGTH);
            int actual = Math.min(remaining, next);
            boolean direction = random.nextBoolean();

            Integer first = 
                    MIN_ELEMENT + 
                    random.nextInt(MAX_ELEMENT - MIN_ELEMENT + 1);

            array[index++] = first;
            int step = 1 + random.nextInt(5);

            if (direction) {
                for (int i = 1; i < actual; ++i) {
                    array[index++] = first + i * step;
                }
            } else {
                for (int i = 1; i < actual; ++i) {
                    array[index++] = first - i * step;
                }
            }
        }

        return array;
    }

    private static final Integer[] getRunnyArray(int length,
                                                 int runLength, 
                                                 Random random) {
        Integer[] array = getRandomArray(length, random);

        int index = 0;

        while (index < length) {
            int remaining = length - index;
            int requested = random.nextInt(runLength);
            int actual = Math.min(remaining, requested);

            Arrays.sort(array, index, index + actual);
            index += actual;
        }

        return array;
    }

    private static final Integer[] getAscendingArray(int length) {
        Integer[] array = new Integer[length];

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

        return array;
    }

    private static void blockify(Integer[] array,
                                 int numberOfBlocks, 
                                 Random random) {
        int blockSize = array.length / numberOfBlocks;
        Integer[][] blocks = new Integer[numberOfBlocks][];

        for (int i = 0; i < numberOfBlocks - 1; ++i) {
            blocks[i] = new Integer[blockSize];
        }

        blocks[numberOfBlocks - 1] = 
                new Integer[blockSize + array.length % blockSize];

        int index = 0;

        for (Integer[] block : blocks) {
            for (int i = 0; i < block.length; ++i) {
                block[i] = array[index++];
            }
        }

        shuffle(blocks, random);

        index = 0;

        for (Integer[] block : blocks) {
            for (int i = 0; i < block.length; ++i) {
                array[index++] = block[i];
            }
        }
    }

    private static void shuffle(Integer[][] blocks, Random random) {
        for (int i = 0; i < blocks.length; ++i) {
            int index1 = random.nextInt(blocks.length);
            int index2 = random.nextInt(blocks.length);
            Integer[] block = blocks[index1];
            blocks[index1] = blocks[index2];
            blocks[index2] = block;
        }
    }
}

AdaptiveMergesortTest.java

package net.coderodde.util;

import java.util.Arrays;
import java.util.Random;
import org.junit.Test;
import static org.junit.Assert.*;

public final class AdaptiveMergesortTest {

    private static final int BRUTE_FORCE_ITERATIONS = 1000;
    private static final int MAXIMUM_ARRAY_LENGTH = 100;
    private static final int MIN_ELEMENT = -50;
    private static final int MAX_ELEMENT = 50;
    private static final int MINIMUM_ARRAY_LENGTH = 3;

    @Test
    public void testBruteForce() {
        long seed = System.currentTimeMillis();
        Random random = new Random(seed);

        System.out.println("AdaptiveMergesortTest.testBruteForce(): seed = " +
                seed);

        for (int i = 0; i < BRUTE_FORCE_ITERATIONS; ++i) {
            int arrayLength = random.nextInt(MAXIMUM_ARRAY_LENGTH + 1);
            arrayLength = Math.max(arrayLength, MINIMUM_ARRAY_LENGTH);

            int fromIndex = random.nextInt(arrayLength / 2);
            int toIndex = arrayLength - random.nextInt(arrayLength / 2);
            Integer[] array1 = getRandomArray(arrayLength, random);
            Integer[] array2 = array1.clone();

            Arrays.sort(array1, fromIndex, toIndex);
            AdaptiveMergesort.sort(array2, fromIndex, toIndex);

            assertTrue(Arrays.equals(array1, array2));
        }
    }

    @Test(expected = NullPointerException.class)
    public void throwsOnNullArray() {
        AdaptiveMergesort.sort(null);
    }

    @Test(expected = IllegalArgumentException.class)
    public void testThrowsOnReversedFromIndexToIndex() {
        AdaptiveMergesort.sort(new Integer[]{ 1, 2, 3 }, 1, 0);
    }

    @Test(expected = IndexOutOfBoundsException.class)
    public void testThrowsOnNegativeFromIndex() {
        AdaptiveMergesort.sort(new Integer[]{ 1, 2, 3}, -1, 2);
    }

    @Test(expected = IndexOutOfBoundsException.class)
    public void testThrowsOnTooLargeToIndex() {
        AdaptiveMergesort.sort(new Integer[]{ 1, 2, 3 }, 1, 4);
    }

    @Test
    public void testEmptyArrayWithIndices() {
        Integer[] array = { 4, 1, 8, 2 };

        for (int i = 0; i < array.length; ++i) {
            AdaptiveMergesort.sort(array, i, i);
        }

        assertTrue(Arrays.equals(array, new Integer[]{ 4, 1, 8, 2}));
    }

    @Test
    public void testOneElementArrayWithIndices() {
        Integer[] array = { 8, 3, 6, 1 };

        for (int i = 0; i < array.length - 1; ++i) {
            AdaptiveMergesort.sort(array, i, i + 1);
        }

        assertTrue(Arrays.equals(array, new Integer[]{ 8, 3, 6, 1}));
    }

    @Test
    public void testEmptyArray() {
        Integer[] array = {};
        AdaptiveMergesort.sort(array);
    }

    @Test
    public void testOneElementArray() {
        Integer[] array = { 0 };
        AdaptiveMergesort.sort(array);
        assertTrue(Arrays.equals(array, new Integer[]{ 0 }));
    }

    private static Integer[] getRandomArray(int length, Random random) {
        Integer[] array = new Integer[length];

        for (int i = 0; i < length; ++i) {
            array[i] = MIN_ELEMENT + 
                       random.nextInt(MAX_ELEMENT - MIN_ELEMENT + 1);
        }

        return array;
    }
}

Sample output

It is slow on larger arrays, yet on mid-sized arrays it performs well.

Seed = 1508092238415
Warming up...
Warming up done!


--- Blocked array ---
Arrays.sort in 12 milliseconds.
AdaptiveMergesort.sort in 7 milliseconds.
Algorithms agree: true
--- Random array ----
Arrays.sort in 134 milliseconds.
AdaptiveMergesort.sort in 78 milliseconds.
Algorithms agree: true
--- Funny array -----
Arrays.sort in 47 milliseconds.
AdaptiveMergesort.sort in 24 milliseconds.
Algorithms agree: true
--- Runny array -----
Arrays.sort in 71 milliseconds.
AdaptiveMergesort.sort in 32 milliseconds.
Algorithms agree: true

Critique request

Please tell me anything that comes to mind.

\$\endgroup\$
3
\$\begingroup\$
        int runsLeft = queue.size();

        while (queue.size() > 1) {
            switch (runsLeft) {
                case 1:
                    // Bounce the lonely leftover run back to the tail of the 
                    // queue:
                    queue.enqueue(queue.dequeue());
                    // Fall through!

                case 0:
                    runsLeft = queue.size();
                    continue;
            }

            Run run1 = queue.dequeue();
            Run run2 = queue.dequeue();
            queue.enqueue(merge(aux, run1, run2));
        }

My first instinct was that this is buggy: I'm still not sure whether it's buggy or merely over-complicated.

Let R be the initial value of runsLeft. If we enter the while loop then it's because R > 1, so neither of the cases in the switch (which IMO should have an explicit default for clarity) are ever executed, and runsLeft will never change. Therefore the entire switch block could be removed without affecting the behaviour of the code.

Should it be switch (runsLeft--)?


        if (headInterval1 != null) {
            mergedRunTail.next = headInterval1;
            headInterval1.prev = mergedRunTail;
            mergedRunTail = headInterval1;
        } else {
            mergedRunTail.next = headInterval2;
            headInterval2.prev = mergedRunTail;
            mergedRunTail = headInterval2;
        }

KISS:

        mergedRunTail.next = headInterval1 != null ? headInterval1
                                                   : headInterval2;
        mergedRunTail.next.prev = mergedRunTail;
        mergedRunTail = mergedRunTail.next;

I've looked over the rest of the code briefly, but without any comments I didn't have much idea of what it was trying to do, and I didn't feel like reverse engineering it.

\$\endgroup\$
  • \$\begingroup\$ You are right, it should have been runsLeft -= 2. It did not affect the correctness of the sort, but it was unstable. \$\endgroup\$ – coderodde Oct 16 '17 at 9:18

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.