Реализация Timsort на Джаве

package practice4.strategies;
 
import java.util.Arrays;
import java.util.Vector;
 
import static java.lang.Math.min;
 
/**
 * created by Vasilenko.K
 */
public class TimSortStrategy <T> implements SortStrategy<T> {
    @Override
    public void sortAsc(Comparable<T>[] a) {
        timsort(a);
    }
 
    private void timsort(Comparable<T>[] a){
        int N = a.length;
 
        int minrun = getMinrun(N);
 
        Vector<Range> minrunStack = new Vector<>();
 
        int currentIndex = 0;
 
        while (currentIndex < N-1) {
            int currentRunIndex = currentIndex;
            int nextIndex = currentRunIndex + 1;
 
            if (a[currentRunIndex].compareTo((T)a[nextIndex]) > 0) {
                exch(a, currentRunIndex, nextIndex);
            }
            boolean goNext = true;
 
            while (goNext) {
                if (a[currentRunIndex].compareTo((T)a[nextIndex-1]) > 0 || currentRunIndex == N-1) {
                    goNext = false;
                }else if (currentRunIndex-currentIndex < minrun)
                    goNext = true;
                if (goNext) {
                    ++currentRunIndex;
                    ++nextIndex;
                }
            }
 
            sortInsertionPart(a, currentIndex, currentRunIndex+1);
            Range r = new Range();
            r.start = currentIndex;
            r.length = currentRunIndex - currentIndex;
 
            minrunStack.add(r);
 
            currentIndex = currentRunIndex;
        }
 
        while (minrunStack.size() > 1)
        {
            Range x = minrunStack.elementAt(0);
            minrunStack.remove(minrunStack.firstElement());
            Range y = minrunStack.elementAt(0);
            minrunStack.remove(minrunStack.firstElement());
            if (x.start > y.start) {
                int temp = x.start;
                x.start = y.start;
                y.start = temp;
 
                temp = x.length;
                x.length = y.length;
                y.length = temp;
            }
            if (y.start != x.start+x.length)
            {
                minrunStack.add(y);
                minrunStack.add(x);
                continue;
            }
            merge(a, x.start, x.length, y.start, y.length);
            x.length = x.length + y.length;
            minrunStack.add(x);
        }
    }
 
    private void sortInsertionPart(Comparable<T>[] a, int start, int end) {
        for (int i = start+1; i < end; ++i) {
            T current = (T)a[i];
            int j = i - 1;
            while ((j >= start) && (a[j].compareTo(current) > 0)) {
                exch(a, j, j+1);
                --j;
            }
        }
    }
    private static int getMinrun(int n) {
        int r = 0;/* станет 1 если среди сдвинутых битов будет хотя бы 1 ненулевой */
        while (n >= 64) {
            r |= n & 1;
            n >>= 1;
        }
        return n + r;
    }
    private void merge(Comparable<T>[] array, int fStart, int fLength, int sStart, int sLength) {
        Comparable<T>[] tmp;
 
        tmp = Arrays.copyOfRange(array, fStart, fLength);
        int fIndex = 0;
        int sIndex = sStart;
        int i = fStart;
 
        while (i < sStart+sLength-1)
        {
            if (array[sIndex].compareTo((T)tmp[fIndex]) > 0)
            {
                array[i] = tmp[fIndex];
                ++fIndex;
                fIndex = min(fIndex, fLength);
            }
            else if (array[sIndex].compareTo((T)tmp[fIndex]) <= 0)
            {
                array[i] = array[sIndex];
                ++sIndex;
                sIndex = min(sIndex, sStart+sLength);
            }
            if (sIndex == sStart + sLength)
            {
                if (fIndex != fLength)
                {
                    System.arraycopy(array, i+1, tmp, fIndex, fLength-fIndex);
 
                    i = sStart+sLength;
                }
            }
            if (fIndex == fLength)
            {
                i = sStart+sLength;
            }
            ++i;
        }
    }
    static class Range {
        int start;
        int length;
        public Range(){
        }
    }
 
}

package practice4.strategies;
 
/**
 * created by Vasilenko.K
 */
public interface SortStrategy <T>{
    default void exch(Comparable<T>[] a, int i, int j){
        Comparable<T> swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
 
    void sortAsc(Comparable<T>[] a);
}