Method sort

src/main/java/com/thealgorithms/sorts/SmoothSort.java:40–107

Sorts the given array in ascending order using Smooth Sort. @param array the array to sort @param the element type @return the sorted array

(final T[] array)

     * @return the sorted array
     */
    @Override
    public <T extends Comparable<T>> T[] sort(final T[] array) {
        if (array.length < 2) {
            return array;
        }

        final int last = array.length - 1;

        // The forest shape is encoded as (p, pshift): p is a bit-vector of present tree orders,
        // shifted right by pshift. pshift is the order of the rightmost (current) Leonardo tree.
        long p = 1L;
        int pshift = 1;

        int head = 0;
        while (head < last) {
            if ((p & 3L) == 3L) {
                sift(array, pshift, head);
                p >>>= 2;
                pshift += 2;
            } else {
                // Add a new singleton tree; if it will not be merged anymore, we must fully trinkle.
                if (LEONARDO[pshift - 1] >= last - head) {
                    trinkle(array, p, pshift, head, false);
                } else {
                    // This tree will be merged later, so it is enough to restore its internal heap property.
                    sift(array, pshift, head);
                }

                if (pshift == 1) {
                    // If L(1) is used, the new singleton is L(0).
                    p <<= 1;
                    pshift = 0;
                } else {
                    // Otherwise, shift to order 1 and append a singleton of order 1.
                    p <<= (pshift - 1);
                    pshift = 1;
                }
            }

            p |= 1L;
            head++;
        }

        trinkle(array, p, pshift, head, false);

        // Repeatedly remove the maximum (always at head) by shrinking the heap region.
        while (pshift != 1 || p != 1L) {
            if (pshift <= 1) {
                // Rightmost tree is a singleton (order 0 or 1). Move to the previous tree root.
                final long mask = p & ~1L;
                final int shift = Long.numberOfTrailingZeros(mask);
                p >>>= shift;
                pshift += shift;
            } else {
                // Split a tree of order (pshift) into two children trees of orders (pshift-1) and (pshift-2).
                p <<= 2;
                p ^= 7L;
                pshift -= 2;