MergeSort和insertionSort组合算法一起运行比单独运行慢，但应该运行得更快

我有一个mergesor，它需要切换到特定数字的insertionSort，这是我的阈值。但我的阈值只能是1、2或3，因为在任何其他情况下，我的合并都会变得非常缓慢。我似乎无法让代码协同工作。

这是我的代码：

public class InsertionSort {
// I haven't found the right Threshold yet, but it should work with any number between 1-100.
public final static int M = 16;
private void Merge(int arr[], int left, int mid, int right) {
int size1 = mid - left + 1;
int size2 = right - mid;
int LeftArray[] = new int[size1];
int RightArray[] = new int[size2];
for (int i = 0; i < size1; ++i) {
LeftArray[i] = arr[left + i];
}
for (int j = 0; j < size2; ++j) {
RightArray[j] = arr[mid + 1 + j];
}
int i = 0;
int j = 0;
int k = left;
while (i < size1 && j < size2) { 
if (LeftArray[i] <= RightArray[j]) {
arr[k] = LeftArray[i];
i++;
} else {
arr[k] = RightArray[j];
j++;
}
k++;
}

while (i < size1) {
arr[k] = LeftArray[i];
i++;
k++;
}
while (j < size2) {
arr[k] = RightArray[j];
j++;
k++;
}
}
public void MergeSort(int arr[], int left, int right, int M) {
if ( left < right ) {
int mid = (left + right) / 2;
MergeSort(arr, left, mid, M);
MergeSort(arr, (mid+1), right, M);
Merge(arr, left, mid, right);
} else if ((right - left + 1) <= M)  {
insertion_sort(arr, left, right);
}}

static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
static int[] readIntfile(String filename) throws Exception {
// Read file into a byte array, and then combine every group of four bytes to an
// int. (Not
// the standard way, but it works!)
byte[] bytes = Files.readAllBytes(Paths.get(filename));
int[] ints = new int[bytes.length / 4];
for (int i = 0; i < ints.length; i++) {
for (int j = 0; j < 4; j++) {
ints[i] += (bytes[i * 4 + j] & 255) << (3 - j) * 8;
}
}
return ints;
}
public static void insertion_sort(int a[], int left, int right) {
int j;
for (int i = left; i <= right; i++) {
int tmp = a[i];
for (j = i; j > 0 && tmp < a[j - 1]; j--) {
a[j] = a[j - 1];
}
a[j] = tmp;
}
}

public static void main(String args[]) throws Exception {
// I have texfile named this with 1000000 numbers
int arr[] = readIntfile("smallints");
// you can also try with this array for example
// int arr[] = {3, 6, 4, 8, 500, 1, 5, 10, 7, 9, 0, 2, 100, 300, 1000, 20, 13, 17, 55, 93};
InsertionSort insert = new InsertionSort();
long before = System.currentTimeMillis();
insert.MergeSort(arr, 0, arr.length-1, M);
long after = System.currentTimeMillis();
printArray(arr);
System.out.println("n" + "Done " + ((after - before) / 1000.0 + " sek"));
}
}