老师，我发现优化后，还是自顶向下的归并排序快，是什么原因呢

我使用了模板类进行封装，自定义了一个testManyTimesSort来测试数组元素数量剩余num个的时候，调用插入排序后的总时间

我选择的num是16，因为经过测试，千万级别，百万级别这样的数量，16个确实是插入排序性能最优的

帮忙看下是什么原因自顶向下的归并排序快

代码如下

#pragma once
#include <algorithm>

template<typename T>
class MergeSort
{
public:
static void mergeSort(T arr[],int n,int num);
static void mergeSortBU(T arr[], int n,int num);
private:
	static	void __mergeSort(T arr[],T aux[],int l,int r,int num);
	static	void __merge(T arr[], T aux[],int l,int mid, int r);
};

template<typename T>
void MergeSort<T>::mergeSort(T arr[], int n,int num)
{
	T *aux = new T[n];
	__mergeSort(arr,aux,0,n-1,num);
	delete []aux;
	aux=NULL;
}

template<typename T>
void MergeSort<T>::mergeSortBU(T arr[], int n,int num)
{
	T *aux = new T[n];
	for (int sz = 1;sz < n;sz += sz)
	{
		for (int i = 0;i+sz < n;i += sz + sz)
		{

			if (n <= 16)
			{
				insertionSort(arr, 0, n);
			}
			if (arr[i + sz - 1]>arr[i + sz])
			{
				__merge(arr, aux, i, i + sz - 1, min(i + sz + sz - 1, n - 1));
			}
		}
	}
	delete[]aux;
	aux = NULL;
}

template<typename T>
void MergeSort<T>::__mergeSort(T arr[],T aux[], int l, int r,int num)
{
	if (l >= r)
	{
		return;
	}
	if (r - l <= num)
	{
		insertionSort(arr,l,r);
	}

	int mid=(l+r)/2;
	__mergeSort(arr,aux,l,mid,num);							//切
	__mergeSort(arr,aux,mid+1,r,num);						//并
	if(arr[mid]>arr[mid+1])
	{
	__merge(arr,aux,l,mid,r);							//排序
	}
}

template<typename T>
void MergeSort<T>::__merge(T arr[],T aux[], int l, int mid, int r)
{
	
	for (int i = l;i <= r;i++)
	{
		aux[i-l]=arr[i];
	}
	int i=l,j=mid+1;
	for (int k = l;k <= r;k++)
	{
		if (i > mid)
		{
			arr[k]=aux[j-l];
			j++;
		}
		else if(j>r)
		{
			arr[k]=aux[i-l];
			i++;
		}
		else if (aux[i - l] < aux[j - l])
		{
			arr[k] = aux[i-l];
			i++;
		}
		else
		{
			arr[k]=aux[j-l];
			j++;
		}
	}
}

#pragma once
#pragma warning(disable:4996)
//#define _SCL_SECURE_NO_WARNINGS

#include <iostream>	

#include <string>	
#include <time.h>	
#include <ctime>
#include <cassert>
using namespace std;
namespace SortTestHelper
{
	int *generateRandomArray(int n, int rangeL, int rangeR)
	{
		assert(rangeL <= rangeR);
		int *arr=new int[n];
		srand((unsigned)time(NULL));
		for (int i = 0;i < n;i++)
		{
			arr[i]=rand() % (rangeR-rangeL+1)+rangeL;
		}
		return arr;
	}

	template<typename T>
	void printArray(T arr, int n)
	{
		for (int i = 0;i < n;i++)
		{
			cout << arr[i] << " ";
		}
		cout << endl;
	}

	template<typename T>
	void testsort(string sortName, void(*sort)(T[], int), T arr[], int n)
	{
		clock_t startTime = clock();
		sort(arr,n);
		clock_t endTime = clock();
		assert(isSorted(arr,n));
		cout <<sortName<<":"  << double(endTime-startTime)/CLOCKS_PER_SEC<<"s"<<endl;
	}

	template<typename T>
	void testManyTimesSort(string sortName, void(*sort)(T[], int,int), T arr[], int n,int num)
	{
		clock_t startTime = clock();
		sort(arr, n,num);
		clock_t endTime = clock();
		assert(isSorted(arr, n));
		cout << sortName << ":" << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	}

	template<typename T>
	bool isSorted(T arr[], int n)
	{
		for (int i = 0;i < n-1;i++)
		{
			if (arr[i] > arr[i+1])
			{
				return false;
			}
		}
		return true;
	}

	int *copyIntArray(int a[], int n)
	{
		int *arr=new int[n];
		copy(a,a+n,arr);
		return arr;
	}
	int *generateNearlyOrderedArray(int n, int swapTimes)
	{
		int *arr=new int[n];
		for (int i = 0;i < n;i++)
		{
			arr[i]=i;
		}
		srand((unsigned)time(NULL));
		for (int i = 0;i < swapTimes;i++)
		{
			int A=rand()%n;
			int B = rand() % n;
			swap(arr[A],arr[B]);
		}
		return arr;
	}
}

#include <iostream>	
#include <string>	
#include <ctime>	
#include "InsertionSort.h"
#include "SelectionSort.h"
#include "SortTestHelper.h"

//#include "MergeSort_maybe.h"
#include "MergeSort.h"

#include "MergeSort_Tercher.h"

using namespace std;




int main()
{

	int n = 1000000;
	int swapTimes=100;
	
	while(true)
	{
		getchar();
		int *arr = SortTestHelper::generateRandomArray(n, 0, n);
		int *arr2 = SortTestHelper::copyIntArray(arr, n);
		int *arr3 = SortTestHelper::generateNearlyOrderedArray(n, swapTimes);
		int *arr4 = SortTestHelper::generateNearlyOrderedArray(n, swapTimes);
		int *arr5 = SortTestHelper::copyIntArray(arr, n);
		

		//SortTestHelper::testsort("mergeSort", &MergeSort<int>::mergeSort, arr,n);
		//SortTestHelper::testsort("mergeSort", &MergeSort<int>::mergeSortBU, arr2, n);
		//SortTestHelper::testsort("mergeSort", mergeSort, arr2, n);
		//SortTestHelper::testsort("insertionSort", insertionSort, arr, n);
		//SortTestHelper::testsort("insertionSort", insertionSort, arr2, n);
		//SortTestHelper::testsort("insertionSort", insertionSort, arr4, n);
		//SortTestHelper::testsort("selectionSort", selectionSort, arr3, n);
		for(int i=16;i<200;i++)
		{
		for(int j=0;j<10;j++)
		{
		int *arr6 = SortTestHelper::copyIntArray(arr, n);
		int *arr7 = SortTestHelper::copyIntArray(arr, n);
		cout << i << ".";
		SortTestHelper::testManyTimesSort("mergeSort  ", &MergeSort<int>::mergeSort, arr6, n,i);
		
		cout << i << ".";
		SortTestHelper::testManyTimesSort("mergeSortBU", &MergeSort<int>::mergeSortBU, arr7, n, i);
		cout << endl;
		delete []arr6;
		arr6 = NULL;
		delete[]arr7;
		arr7 = NULL;
		}
		}

		delete[]arr;
		arr = NULL;
		delete[]arr2;
		arr2 = NULL;
		delete[]arr3;
		arr3 = NULL;
		delete[]arr4;
		arr4 = NULL;
		delete[]arr5;
		arr5 = NULL;
	}


}