I have this sorting algorithm which constructs an (unbalanced) tree and performs in-order traversal in order to sort the requested range. However, the more order exists in the input array, the closer to time complexity of \$\Theta(n^2)\$ it will get, yet it runs in \$\Theta(n \log n)\$ on most randomly generated arrays.package net.coderodde.util;import java.util.Arrays;import java.util.Iterator;import java.util.Random;/** * This class holds some static sorting methods. *  * @author Rodion Efremov * @version 1.6 */public class CoderoddeArrays {    /**     * This class represents an unbalanced binary search tree. Provides only     * minimum functionality needed in Treesort algorithm. It performs well     * on randomly generated data, but may degrade to a quadratic time sort on     * arrays with lots of pre-existing order. (On ascending/descending array it     * will degrade to quadratic time.)     *     * @param <E> the element type.     */    private static class Tree<E extends Comparable<? super E>>     implements Iterable<E> {        static class Node<E extends Comparable<? super E>> {            E value;            Node<E> left;            Node<E> right;            Node<E> parent;            Node(final E value) {                this.value = value;            }        }        private Node<E> root;        private int size;        /**         * Inserts a value into this <code>Tree</code>.         *         * @param value the value to insert.         */        void insert(final E value) {            Node<E> newNode = new Node<>(value);            if (root == null) {                size = 1;                root = newNode;                return;            }            Node<E> parent = null;            Node<E> current = root;            int cmp = 0;            while (current != null) {                parent = current;                current = (cmp = value.compareTo(current.value)) < 0 ?                          current.left :                          current.right;            }            if (cmp < 0) {                parent.left = newNode;            } else {                parent.right = newNode;            }            newNode.parent = parent;            size++;        }        /**         * Returns the successor node of <code>node</code>.         *         * @param node the node whose successor to search.         *         * @return the successor node of <code>node</code> or <code>null</code>         * if <code>node</code> is the rightmost node, i.e., has no successor.         */        Node<E> successor(Node<E> node) {            if (node.right == null) {                while (node.parent != null && node.parent.right == node) {                    node = node.parent;                }                if (node.parent == null) {                    return null;                } else {                    return node.parent;                }            }            node = node.right;            while (node.left != null) {                node = node.left;            }            return node;        }        /**         * Gets a tree iterator for this <code>Tree</code>.         *         * @return a tree iterator.         */        public Iterator<E> iterator() {            return new TreeIterator();        }        /**         * This class traverses a <code>Tree</code> in-order.         */        public class TreeIterator implements Iterator<E> {            private int retrieved;            private Node<E> current;            public TreeIterator() {                current = root;                // Go point to the least value node.                if (current != null) {                    while (current.left != null) {                        current = current.left;                    }                }            }            @Override            public boolean hasNext() {                return retrieved < size;            }            @Override            public E next() {                if (retrieved == 0) {                    retrieved = 1;                    return current.value;                }                Node<E> node = successor(current);                current = node;                retrieved++;                return current.value;            }        }    }    /**     * Sorts by means of constructing (an unbalanced) binary tree and traverses     * it in-order.     *     * @param <E>       the element type; should be <code>Comparable</code>.     * @param array     the array whose values to put in order.     * @param fromIndex the staring index of the range to sort.     * @param toIndex   the (exclusive) ending index of the range to sort.     */    public static <E extends Comparable<? super E>>     void sort(final E[] array,               final int fromIndex,               final int toIndex) {        Tree<E> tree = new Tree<>();        // Load the tree.        for (int i = fromIndex; i < toIndex; ++i) {            tree.insert(array[i]);        }        int index = fromIndex;        // In-order traversal.        for (final E element : tree) {            array[index++] = element;        }    }    /**     * Sorts the entire array using Treesort algorithm.     *      * @param <E>   the element type.     * @param array the array to sort.     */    public static <E extends Comparable<? super E>>    void sort(final E[] array) {        sort(array, 0, array.length);    }    private static final int LENGTH = 150000;    private static final int MINIMUM = 300000;    private static final int MAXIMUM = 500000;    public static void main(final String... args) {        final long seed = System.currentTimeMillis();        final Integer[] array1 = getRandomArray(LENGTH,                                                MINIMUM,                                                MAXIMUM,                                                new Random(seed));        final Integer[] array2 = array1.clone();        System.out.println(Seed:  + seed);        long ta = System.currentTimeMillis();        Arrays.sort(array1, 10, array1.length - 10);        long tb = System.currentTimeMillis();        System.out.println(Arrays.sort() in  + (tb - ta) +  ms.);        ta = System.currentTimeMillis();        sort(array2, 10, array2.length - 10);        tb = System.currentTimeMillis();        System.out.println(Treesort in  + (tb - ta) +  ms.);        // Strongly means equal by references. I need this in order to be        // able to assert that Treesort sorts stabily.        System.out.println(Strongly equal:  + stronglyEquals(array1, array2));    }    private static Integer[] getRandomArray(final int length,                                            final int minimum,                                            final int maximum,                                            final Random rnd) {        final Integer[] array = new Integer[length];        for (int i = 0; i < length; ++i) {            array[i] = rnd.nextInt(maximum - minimum + 1) + minimum;        }        return array;    }    private static <E> boolean stronglyEquals(final E[] array1,                                              final E[] array2) {        if (array1.length != array2.length) {            return false;        }        for (int i = 0; i < array1.length; ++i) {            if (array1[i] != array2[i]) {                return false;            }        }        return true;    }}So as always, I am interested in all suggestions out there regarding naming, commenting, formatting, algorithm, and so on.
Treesort in Java
java;sorting;tree