5
\$\begingroup\$

See the next iteration.

I designed and implemented this adaptive heap sort in Java. It works as follows:

  • Copy the range to be sorted into auxiliary array \$A\$
  • Create an empty run heap \$H\$
  • Scan \$A\$ from beginning to the end and whenever we have counted a longest possible run (a run is a longest ascending or descending contiguous subsequence of the input sequence), we store it in \$H\$.
    Each run \$r\$ is encoded by two integers: \$r.from\$ is the index of the first array component in the run, and \$r.to\$ is the index of the last array component in the run. In the run heap, the top element is the run \$r\$, for which \$A[r.from]\$ is minimal (notice the indirection).
  • Then, as long as the run heap is not empty, we remove the top element. This is done by returning \$A[r.from]\$, where \$r\$ is the topmost run in the run heap. After that, we set \$r.from \leftarrow r.from + 1\$, and possibly sift it down in order to restore the indirect heap invariant. If a run is exhausted, it is removed from the heap.

The best case complexity of this sort is \$\Theta(N)\$. The worst case complexity is \$\Theta(N \log N)\$. Linear space complexity and is unstable (may reorder the equal elements) due to heap structure.

HeapSelectionSort.java:

package net.coderodde.util.sorting;

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

/**
 * This class implements a sorting algorithm called 
 * <b><i>heap selection sort</i></b>. The worst case complexity is linearithmic
 * O(n log n), best case complexity linear O(n). Linear space complexity and is
 * unstable.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public class HeapSelectionSort {

    /**
     * Sorts the range {@code array[fromIndex], array[fromIndex + 1], ...,
     * array[toIndex - 2], array[toIndex - 1]} using the specified comparator.
     * 
     * @param <T>        the array component type.
     * @param array      the array holding the range to sort.
     * @param fromIndex  the starting (inclusive) index of the range to sort.
     * @param toIndex    the ending (exclusive) index of the range to sort.
     * @param comparator the array component comparator.
     */
    public static <T> void sort(T[] array, 
                                int fromIndex, 
                                int toIndex, 
                                Comparator<? super T> comparator) {
        rangeCheck(array.length, fromIndex, toIndex);

        if (toIndex - fromIndex < 2) {
            return;
        }

        T[] aux = Arrays.copyOfRange(array, fromIndex, toIndex);
        Heap<T> heap = createHeap(aux, comparator);

        for (; fromIndex < toIndex; ++fromIndex) {
            array[fromIndex] = heap.popElement();
        }
    }

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

    /**
     * Sorts the range {@code array[fromIndex], array[fromIndex + 1], ...,
     * array[toIndex - 2], array[toIndex - 1]} using the natural comparator.
     * 
     * @param <T>        the array component type.
     * @param array      the array holding the range to sort.
     * @param fromIndex  the starting (inclusive) index of the range to sort.
     * @param toIndex    the ending (exclusive) index of the range to sort.
     */
    public static <T> void sort(T[] array, int fromIndex, int toIndex) {
        sort(array, fromIndex, toIndex, NaturalOrder.INSTANCE);
    }

    /**
     * Sorts the entire array using the natural comparator.
     * 
     * @param <T>        the array component type.
     * @param array      the array holding the range to sort.
     */
    public static <T> void sort(T[] array) {
        sort(array, 0, array.length);
    }

    private static <T> Heap<T> createHeap(T[] array, 
                                          Comparator<? super T> comparator) {
        Heap<T> heap = new Heap<>(array.length / 2 + 1, array, comparator);

        int head;
        int left = 0;
        int right = 1;
        int last = array.length - 1;

        while (left < last) {
            head = left;

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

                heap.pushRun(new Run(head, left));
            } else {
                // Scanning descending run.
                while (left < last
                        && comparator.compare(array[left], array[right]) >= 0) {
                    ++left;
                    ++right;
                }

                Run run = new Run(head, left);
                reverseRun(array, run);
                heap.pushRun(run);
            }

            ++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) {
            heap.pushRun(new Run(left, left));
        }

        return heap;
    }

    private static class Run {
        int from;
        int to;

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

    private static class Heap<T> {
        private int size;
        private final T[] array;
        private final Run[] runs;
        private final Comparator<? super T> comparator;

        Heap(int size, T[] array, Comparator<? super T> comparator) {
            this.runs = new Run[size];
            this.array = array;
            this.comparator = comparator;
        }

        T popElement() {
            T ret = array[runs[0].from];

            if (runs[0].from == runs[0].to) {
                // The run at the head of the heap is fully processed, remove.
                Run last = runs[--size];
                runs[0] = last;
            } else {
                // Increment to the next element.
                ++runs[0].from;
            }

            // Possibly sift down the top element in order to restore the
            // heap invariant.
            siftDown();
            return ret;
        }

        void pushRun(Run run) {
            int nodeIndex = size++;
            runs[nodeIndex] = run;
            siftUp(nodeIndex);
        }

        void siftUp(int index) {
            Run target = runs[index];

            for (;;) {
                int parentIndex = (index - 1) >> 1;

                if (parentIndex < 0) {
                    runs[0] = target;
                    return;
                }

                if (comparator.compare(array[runs[parentIndex].from], 
                                       array[target.from]) > 0) {
                    runs[index] = runs[parentIndex];
                    index = parentIndex;
                } else {
                    runs[index] = target;
                    return;
                }
            }
        }

        private void siftDown() {
            int nodeIndex = 0;
            int leftChildIndex = 1;
            int rightChildIndex = 2;
            int minIndex = 0;

            for (;;) {
                if (leftChildIndex < size 
                        && comparator.compare(array[runs[leftChildIndex].from], 
                                              array[runs[nodeIndex].from]) < 0) {
                    minIndex = leftChildIndex;
                }

                if (rightChildIndex < size
                        && comparator.compare(array[runs[rightChildIndex].from], 
                                              array[runs[minIndex].from]) < 0) {
                    minIndex = rightChildIndex;
                }

                if (minIndex == nodeIndex) {
                    return;
                }

                Run run = runs[minIndex];
                runs[minIndex] = runs[nodeIndex];
                runs[nodeIndex] = run;

                nodeIndex = minIndex;
                leftChildIndex = (nodeIndex << 1) + 1;
                rightChildIndex = leftChildIndex + 1;
            }
        }
    }

    private static <T> void reverseRun(T[] array, Run run) {
        for (int i = run.from, j = run.to; i < j; ++i, --j) {
            T tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
    }

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

        if (fromIndex < 0) {
            throw new ArrayIndexOutOfBoundsException(
                    "'fromIndex' is negative: " + fromIndex);
        }

        if (toIndex > arrayLength) {
            throw new ArrayIndexOutOfBoundsException(
                    "'toIndex' is too large: " + toIndex + ", array length: " +
                    arrayLength);
        }
    }

    private static final class NaturalOrder implements Comparator<Object> {

        @SuppressWarnings("unchecked")
        @Override
        public int compare(Object first, Object second) {
            return ((Comparable<Object>) first).compareTo(second);
        }

        private static final NaturalOrder INSTANCE = new NaturalOrder();
    }
}

Demo.java:

package net.coderodde.util.sorting;

import java.util.Arrays;
import java.util.Objects;
import java.util.Random;
import static net.coderodde.util.sorting.HeapSelectionSort.sort;

public class Demo {

    public static void main(final String... args) {
        int size = 500000;
        long seed = System.currentTimeMillis();
        Random random = new Random(seed);
        Integer[] array1 = createRandomIntegerArray(size, random);
        Integer[] array2 = array1.clone();

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

        int fromIndex = 2;
        int toIndex = size - 2;

        //// Random arrays.
        System.out.println("--- Random integer array ---");

        long ta = System.currentTimeMillis();
        Arrays.sort(array1, fromIndex, toIndex, Integer::compare);
        long tb = System.currentTimeMillis();

        System.out.println("java.util.Arrays.sort in " + (tb - ta) + 
                           " ms. Sorted: " + 
                           isSorted(array1, fromIndex, toIndex));

        ta = System.currentTimeMillis();
        sort(array2, fromIndex, toIndex, Integer::compare);
        tb = System.currentTimeMillis();

        System.out.println("Heap selection sort in " + (tb - ta) +
                           " ms. Sorted: " + 
                           isSorted(array2, fromIndex, toIndex));

        System.out.println("Array contents same: " + arraysEqual(array1,
                                                                 array2)); 
        // Presorted arrays.
        array1 = createPresortedArray(size, 23);
        array2 = array1.clone();

        System.out.println("--- Presorted array ---");

        ta = System.currentTimeMillis();
        Arrays.sort(array1, fromIndex, toIndex, Integer::compare);
        tb = System.currentTimeMillis();

        System.out.println("java.util.Arrays.sort in " + (tb - ta) + 
                           " ms. Sorted: " + 
                           isSorted(array1, fromIndex, toIndex));

        ta = System.currentTimeMillis();
        sort(array2, fromIndex, toIndex, Integer::compare);
        tb = System.currentTimeMillis();

        System.out.println("Heap selection sort in " + (tb - ta) +
                           " ms. Sorted: " + 
                           isSorted(array2, fromIndex, toIndex));

        System.out.println("Array contents same: " + arraysEqual(array1,
                                                                 array2));
    }

    private static Integer[] createRandomIntegerArray(int size, Random random) {
        Integer[] ret = new Integer[size];

        for (int i = 0; i < size; ++i) {
            ret[i] = random.nextInt(size / 2);
        }

        return ret;
    }

    private static Integer[] createPresortedArray(int size, int runs) {
        Integer[] ret = createRandomIntegerArray(size, new Random());
        int runLength = size / runs;

        for (int i = 0; i < runs; ++i) {
            Arrays.sort(ret, runLength * i, 
                        Math.min(size, runLength * (i + 1)));
        }

        return ret;
    }

    private static boolean isSorted(Integer[] array, 
                                    int fromIndex, 
                                    int toIndex) {
        for (int i = fromIndex; i < toIndex - 1; ++i) {
            if (array[i].compareTo(array[i + 1]) > 0) {
                return false;
            }
        }

        return true;
    }

    private static <T> boolean arraysEqual(T[] array1, T[] array2) {
        if (array1.length != array2.length) {
            return false;
        }

        for (int i = 0; i < array1.length; ++i) {
            if (!Objects.equals(array1[i], array2[i])) {
                return false;
            }
        }

        return true;
    }    
}

So, what do you think?

Have you seen this algorithm discussed in computer scientific literature?

\$\endgroup\$
2
\$\begingroup\$

This algorithm is new to me (which doesn't mean much) and it looks interesting. But you need do some comparisons in order to get famous (:D). How is the performance when compared to the stable Collections.sort? I can see that your Demo measures it, but for us, lazy people, you should present the results.

HeapSelectionSort

createHeap

The first confusing bit was for me

   int left = 0;
   int right = 1;

I guess, left + 1 == right is an invariant and eliminating one of them could make it more readable. This should be easily possible.

private static class Heap {

I'd call it RunHeap<T> as Heap<T> has a well-known meaning.

siftDown

       int rightChildIndex = 2;
       ...
           rightChildIndex = leftChildIndex + 1;

I'd define it inside the loop like

        int rightChildIndex = leftChildIndex + 1;

and save one line.


array[runs[leftChildIndex].from]

This gets repeated a lot and could use a method like

T getFromObject(int index) {
    return array[runs[index].from]
}

Demo

You should repeat your measurements a few times in order to see how well it runs when fully compiled.

You could also create a Comparator counting how many times it's been called. This is hacky, but could give you valuable information about how you're doing.


   long seed = System.currentTimeMillis();
   Random random = new Random(seed);

I can see, you're doing it since you want the seed, but I'd use the better build-in randomization like

    final Random random = new Random();
    final long seed = random.nextLong();
    random.setSeed(seed);

Here, it doesn't matter but in general using the millisecond for seeding is far from optimum.


System.out.println("Array contents same: " + arraysEqual(array1, array2)); 

I hope, they're the same. So don't print it, verify it

 if (!arraysEqual(array1, array2)) {
     throw new RuntimeException("Array contents NOT same");
 }

and save yourself something to check manually.

Analysis

I haven't tried it out, but I can see that you're allocation a lot of memory. A copy of the whole to be sorted range and an additional big array for the heap.

In the best case (sorted array), it obviously wastes time, but I'd agree that this case is not worth optimizing. But cases of nearly-sorted arrays may be rather common and you could try to optimize for them. You could use ArrayList<Run> instead of the array (this is obviously not free).

Another thing is the creation of many tiny Runs, which cost a lot of memory and lead to bad memory locality. I've got two ideas:

Decreasing the number of runs

If you encounter two consecutive very short runs, merge them together. Depending on how exactly you do it, you may ensure that there are no more than array.length / 4 + 3 runs or alike.

Eliminating the class

This is very low level, but int + int = long. Put from into the lower part of the long and to into the upper part. Hardly anything will change, your sifting will stay basically the same and you'll save maybe 20 bytes per run and improve your memory locality.

Measurements

This is the output when run 10 times in row:

Seed: 6578457428755244339
--- Random integer array ---
java.util.Arrays.sort in 359 ms.
Heap selection sort in 771 ms.
--- Presorted array ---
java.util.Arrays.sort in 57 ms. Sorted: true
Heap selection sort in 91 ms. Sorted: true
--- Random integer array ---
java.util.Arrays.sort in 142 ms.
Heap selection sort in 675 ms.
--- Presorted array ---
java.util.Arrays.sort in 54 ms. Sorted: true
Heap selection sort in 65 ms. Sorted: true
--- Random integer array ---
java.util.Arrays.sort in 127 ms.
Heap selection sort in 681 ms.
--- Presorted array ---
java.util.Arrays.sort in 60 ms. Sorted: true
Heap selection sort in 67 ms. Sorted: true
--- Random integer array ---
java.util.Arrays.sort in 128 ms.
Heap selection sort in 688 ms.
--- Presorted array ---
java.util.Arrays.sort in 54 ms. Sorted: true
Heap selection sort in 65 ms. Sorted: true
--- Random integer array ---
java.util.Arrays.sort in 130 ms.
Heap selection sort in 698 ms.
--- Presorted array ---
java.util.Arrays.sort in 54 ms. Sorted: true
Heap selection sort in 86 ms. Sorted: true
--- Random integer array ---
java.util.Arrays.sort in 125 ms.
Heap selection sort in 716 ms.
--- Presorted array ---
java.util.Arrays.sort in 54 ms. Sorted: true
Heap selection sort in 70 ms. Sorted: true
--- Random integer array ---
java.util.Arrays.sort in 129 ms.
Heap selection sort in 717 ms.
--- Presorted array ---
java.util.Arrays.sort in 56 ms. Sorted: true
Heap selection sort in 64 ms. Sorted: true
--- Random integer array ---
java.util.Arrays.sort in 132 ms.
Heap selection sort in 708 ms.
--- Presorted array ---
java.util.Arrays.sort in 60 ms. Sorted: true
Heap selection sort in 64 ms. Sorted: true
--- Random integer array ---
java.util.Arrays.sort in 123 ms.
Heap selection sort in 698 ms.
--- Presorted array ---
java.util.Arrays.sort in 53 ms. Sorted: true
Heap selection sort in 62 ms. Sorted: true
--- Random integer array ---
java.util.Arrays.sort in 128 ms.
Heap selection sort in 703 ms.
--- Presorted array ---
java.util.Arrays.sort in 53 ms. Sorted: true
Heap selection sort in 61 ms. Sorted: true

It looks like the standard sort is faster and improves much more over time than your algorithm. I guess, the bad locality is the culprit and this is solvable.

\$\endgroup\$
  • \$\begingroup\$ I am famous (:D) \$\endgroup\$ – coderodde Jul 27 '15 at 14:03
  • \$\begingroup\$ @coderodde I replaced Run by long and got better numbers: Heap selection sort in 719 ms. ... Heap selection sort in 555 ms. (instead of 703 ms). Still too slow, probably because of the runs being short (2.5 on average) and maybe because of the memory indirection overhead. \$\endgroup\$ – maaartinus Jul 27 '15 at 20:08
  • \$\begingroup\$ Yeah, I know. Just like Dijkstra's smoothsort, HSS has impractically large constant factors. :( \$\endgroup\$ – coderodde Jul 28 '15 at 12:28
  • \$\begingroup\$ @coderodde Above I was wrong with "2.5 on average", it's actually 3. Doubling it by merging two consecutive runs should be trivial and so should be lower bounding the minimum run length. This could cut the overhead to something small, but the memory indirection remains. +++ I guess, you could make HSS stable by comparing lexicographically (value, position). +++There's been too many too smart people working on sorting. \$\endgroup\$ – maaartinus Jul 28 '15 at 19:17

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.