Timsort сортировка

package personal.exercise;
import java.util.*;
/**
 *
 * @author Timur
 */
class Timsort20
{
    private final Comparator comparator;
    private final int minrun;
    
    private List<Figure> massive;
    
    private List<Integer> runIndex;
    private int[] runLength;
    private List<int[]> pairList;
 
    public Timsort20(List<Figure> massive, Comparator comparator){
        this.comparator = comparator;
        minrun = 32;
        
        this.massive = massive;
        
        runIndex = new ArrayList<Integer>();
        runIndex.add(0);
        
    }
 
    public List<Figure> Sort()
    {
        if(massive.size() < minrun){
            System.out.println("Массив для сортировки слишком мал");
            return massive;
        }
        
        GetListOfRunIndex();
        Insert_Sort();
        GetListOfRunLength();
        
        pairList = new ArrayList<int[]>();
        for (int i = 0; i < runIndex.size(); i++) {
            pairList.add(new int[]{runIndex.get(i), runLength[i]}); 
        }
        
        Merge_Sort();
        ForceMerge();
        
        return massive;
    }
    private void GetListOfRunIndex()
    {
        boolean monotonne = true;
        boolean increases = false;                                              //Убывает или возрастает нестрого?
 
        if (comparator.compare(massive.get(0),massive.get(1)) != 1){
            increases = true;
        }
 
        for (int i = 1; i < massive.size(); i++){
            if (increases){                                                         //Если подмассив возрастает
                if ((comparator.compare(massive.get(i - 1),massive.get(i)) == 1 | !monotonne)){   //Если возрастание прекратилось
                    if (i - runIndex.get(runIndex.size() - 1)>= minrun){            //Если подмассив больше или равен minrun
                        if (comparator.compare(massive.get(i),massive.get(i + 1)) != 1){
                            increases = true; 
                        } else {
                            increases = false; 
                        }
                        runIndex.add(i);
                        monotonne = true;
                    }else{                                                      //Если подмассив меньше minrun - перестать проверять на продолжение монотонности
                        monotonne = false;
                    }
                }
            }else{
                if (comparator.compare(massive.get(i - 1)/*prev*/,massive.get(i)) != 1 | !monotonne){
                    if (i - runIndex.get(runIndex.size() - 1) >= minrun){
                        for (int j = 0; j < (i - runIndex.get(runIndex.size() - 1)) / 2; j++){      //Инверсия убывающего подмассива
                            Collections.swap(massive, j + runIndex.get(runIndex.size() - 1), i - 1 - j);
                        }
 
                        if (comparator.compare(massive.get(i), massive.get(i + 1)) != 1){
                            increases = true; 
                        } else {
                            increases = false; 
                        }
                        runIndex.add(i);
                        monotonne = true;
                    }
                    else
                    {
                        monotonne = false;
                    }
                }
            }
        }
 
 
        if (massive.size() - 1 - runIndex.get(runIndex.size() - 1) - 1 < minrun)             //если последний подмассив меньше minrun - объединение с предпоследним
        {
            runIndex.remove(runIndex.size() - 1);
        }
    }
 
    private void Insert_Sort()
    {
 
        for (int i = 0; i < runIndex.size() - 1; i++){
            
            for (int n = runIndex.get(i); n < runIndex.get(i+1); n++){
                for (int m = runIndex.get(i); m < n; m++){
                    if (comparator.compare(massive.get(n), massive.get(m)) == -1){
                        Collections.swap(massive, n, m);
                    }
                }
            }
        }
 
        //Сортировка последнего подмассива:
        for (int n = runIndex.get(runIndex.size() - 1); n < massive.size(); n++){
            for (int m = runIndex.get(runIndex.size() - 1); m < n; m++){
                if (comparator.compare(massive.get(n), massive.get(m)) == -1){
                    Collections.swap(massive, n, m);
                }
            }
        }
    }
 
 
    private void GetListOfRunLength()
    {
        runLength = new int[runIndex.size()];
 
        for (int i = 0; i < runIndex.size() - 1; i++)
        {
            runLength[i] = runIndex.get(i+1) - runIndex.get(i);
        }
        runLength[runIndex.size() - 1] = massive.size() - runIndex.get(runIndex.size() - 1);
    }
 
    private void Merge(int[] Pair1, int[] Pair2)
    {
        //Создание времменных массивов из run'ов
        List<Figure> run1 = new ArrayList<Figure>();
        for (int i = 0; i < Pair1[1]; i++) {
            run1.add(massive.get(Pair1[0] + i));
        }
        
        List<Figure> run2 = new ArrayList<Figure>();
        for (int i = 0; i < Pair2[1]; i++) {
            run2.add(massive.get(Pair2[0] + i));
        }
        
        int n = 0;
        int m = 0;
 
        int t = 0;
        int d = 0;
 
        //Заполнение массива упорядочеными элементами из обоих врем. массивов
        while (n < Pair1[1] && m < Pair2[1]){
            if (comparator.compare(run1.get(n), run2.get(m)) == -1){
                if (t > 7){                                                     //Galloping mode
                    int curr = n;
 
                    int i = 0;
                    while (comparator.compare(run1.get(n), run2.get(m)) == -1){
                        i++;
                        n += 2 ^ i;
                        try{
                            Figure check = run1.get(n); 
                        }catch (Exception e){
                            break; 
                        } 
                    }
                    if (i != 0) {
                        n -= 2 ^ i;
                    }
 
                    for (int j = curr; j < n - curr; j++) {
                        massive.set(Pair1[0] + j + m, run1.get(j));
                    }
                }
 
                massive.set(Pair1[0] + n + m, run1.get(n));
                n++;
                d = 0;
                t++;
            }else{
                if (d > 7){  //Galloping mode
                    int curr = m;
 
                    int i = 0;
                    while (comparator.compare(run2.get(m), run1.get(n)) == -1){
                        i++;
                        m += 2 ^ i;
                        try{
                            Figure check = run2.get(m);
                        }catch (Exception e){
                            break; 
                        } 
                    }
                    if (i != 0) {
                        m -= 2 ^ i; 
                    }
 
                    for (int j = curr; j < m - curr; j++) {
                        massive.set(Pair1[0] + j + n, run2.get(j));
                    }
                }
 
                massive.set(Pair1[0] + n + m, run2.get(m));
                m++;
                t = 0;
                d++;
                
            }
        }
 
        //Прицепление остатка от большего
        if (n == run1.size()){
            for (int j = m; j < Pair2[1] - m; j++) {
                massive.set(Pair1[0] + n + j, run2.get(j));
            }
        }else {
            for (int j = n; j < Pair1[1] - n; j++) {
                    massive.set(Pair1[0] + j + m, run1.get(j));
                }
            }
        }
    
 
 
    private void Merge_Sort()
    {
        
        int i = 1;
        while (pairList.size() > 3)
        {
            if (pairList.get(i)[1] > pairList.get(i + 1)[1] + pairList.get(i + 2)[1] & pairList.get(i + 1)[1] > pairList.get(i + 2)[1]) {
                Merge(pairList.get(i - 1), pairList.get(i));
                int[] temp = {pairList.get(i - 1)[0], pairList.get(i - 1)[1] + pairList.get(i)[1]};
                pairList.set(i - 1, temp);
                pairList.remove(i);
            }
            else
            {
                if (pairList.get(i)[1] < pairList.get(i + 2)[1]) {
                    Merge(pairList.get(i), pairList.get(i + 1));
                    int[] temp = {pairList.get(i)[0], pairList.get(i)[1] + pairList.get(i + 1)[1]};
                    pairList.set(i, temp);
                    pairList.remove(i + 1); 
                } else {
                    Merge(pairList.get(i + 1), pairList.get(i + 2));
                    int[] temp = {pairList.get(i + 1)[0], pairList.get(i + 1)[1] + pairList.get(i + 2)[1]};
                    pairList.set(i + 1, temp);
                    pairList.remove(i + 2);
                }
            }
        }
    }
 
    private void ForceMerge()
    {
        while (pairList.size() > 1)
        {
            Merge(pairList.get(0), pairList.get(1));
            int[] temp = {pairList.get(0)[0], pairList.get(0)[1] + pairList.get(1)[1]};
            pairList.set(0, temp);
            pairList.remove(1);
        }
    }
 
}