Возможно ли/жизнеспособно ли завершение алгоритма сортировки слиянием на месте с сортировкой вставками?

Я написал встроенный алгоритм сортировки слиянием для сортировки большого набора данных произвольного размера (100 000 элементов и более). Я думал о том, чтобы добавить сортировку вставками, когда данные почти отсортированы, чтобы алгоритм работал немного быстрее. Мне было интересно, возможно ли это с сортировкой слиянием на месте?

Вот часть моего кода.

public static void merge(ArrayList<String> list, int low, int high) {
   if (low < high) {
        int mid = (low + high) / 2;
        merge(list, low, mid);
        merge(list, mid + 1, high);
        mergeSort(list, low, mid, high);
    }

}

public static void mergeSort(ArrayList<String> list, int first, int mid,
        int last) {
    int left = first;
    int right = mid + 1;
    String holder = "";

    // if mid <= mid+1 skip merge
    if (compareTo(list.get(mid), list.get(right)) <= 0) {
        return;
    }

    while (left <= mid && right <= last) {
        // if left index <= right index then just add to left
        if (compareTo(list.get(left), list.get(right)) <= 0) {
            left++;
        } else {
            holder = list.get(right);
            copyList(list, left, right - left);//moves everything from left to right-left                       up one index in the arraylist
            list.set(left, holder);

            left++;
            mid++;
            right++;
        }
    }
    // what is left is in place

}

public static void copyList(ArrayList<String> source, int srcPos, int length) {
    String temp1 = "";
    String temp2 = source.get(srcPos);
    for (int i = 0; i < length; i++) {
        temp1 = source.get(srcPos + 1);
        source.set(srcPos + 1, temp2);
        temp2 = temp1;
        srcPos++;
    }
}

Теперь я думал о реализации сортировки вставками по счетчику количества элементов, когда я сначала добавляю их в массив, а затем меняю метод слияния на следующий.

public static void merge(ArrayList<String> list, int low, int high) {
   if(high-low==dataSize-1){
        int mid = (low + high) / 2;
        merge(list, low, mid);
        merge(list, mid + 1, high);
        insertionSort(list);
   }else if (low < high) {
        int mid = (low + high) / 2;
        merge(list, low, mid);
        merge(list, mid + 1, high);
        mergeSort(list, low, mid, high);
    }

}

Однако на самом деле это делает мой алгоритм вечностью. Я предполагаю, что делаю это неправильно, и алгоритм использует n ^ 2 для запуска, поскольку данные генерируются полностью случайным образом и почти не отсортированы.

Что я делаю неправильно? Какие-либо предложения? Я предполагаю, что, поскольку он используется для сортировки слиянием, он не будет работать.

Спасибо!