发个排序算法，大家看看怎么优化

template <class T>
void qsort(T* a, int left, int right)
{
if(a == NULL ||  left <0 || right<0)return;
if(left >= right)return;

int last = left;
for(int i=left+1;i<=right;i++)
{
if(a[i]<a[left])
swap<T>(a[i],a[++last]);
}
swap<T>(a[left], a[last]);
qsort<T>(a, left, last-1);
qsort<T>(a,last+1, right);

}

template <class T>
void meger(T*a, int l, int p, int r)
{
int i = 0;
int j = 0;
int k = 0;
T tl[p-l+1];
T tr[r-p];
for(i=l;i<=p;i++){tl[j++] = a[i];}
for(i=p+1;i<=r;i++){tr[k++] = a[i];}

for(j=0,k=0,i=l;i<=r;i++)
{
if(j>p-l && k>r-p-1)break;
else if(j>p-l){a[i]=tr[k++];}
else if(k>r-p-1){a[i]=tl[j++];}
else a[i] = tl[j]<tr[k]?tl[j++]:tr[k++];
}
}
template <class T>
void megersort(T* a, int left, int right)
{
if(left<right)
{
megersort<T>(a, left,(left+right)/2);
megersort<T>(a,(left+right)/2+1,right);
meger<T>(a,left,(left+right)/2,right);
}
}

int main( void )

{
int a[] = {5,4,3,2,1,1,4,0,9};
megersort<int>(a,0,8);
for(int i=0;i<=8;i++)
{
printf("%d, ",a[i]);
}
return 0;
}

性能优化 排序算法
[解决办法]
你这个是递归的归并排序吧。
是化整为零然后再整合的过程。

我觉得非递归的归并排序更有效率。不需要递归的开销，也不需要设置栈来模拟递归。
不需要化整为零这个中间阶段，直接两两归并。
第1次每次取1个数归并，a[0]和a[1]归并，a[2]和a[3]归并....
第2次每次2个数归并，a[0]a[1]和a[2]a[3]归并..
第3次每次4个数归并..
直到整个数组归并成1个。
[解决办法]

引用:

mergesort能做到稳定，这点heapsort/qsort都做不到。光这点本身就够实用了。是不是inplace那是另一个问题。

理论是一码事，实用完全是另一码事。何况他是要写通用工具。

[解决办法]
既然是模板，那么T很可能不是POD，memcpy(tmp,a+i,sizeof(T)*lent);不可靠。

如果要使用T *tmp = (T*)malloc(sizeof(T)*n);分配缓冲区，那么移动时应该使用placement new来调用拷贝构造函数，然后调用源对象的析构函数（以便于后面用拷贝构造函数再移动回去）

如果要使用赋值操作符来移动对象，那么分配缓冲区时应该用new[]操作符以保证对象已经构造。

交替使用原数据和缓冲区进行合并很有必要，可以减少几乎一半的移动次数：

T * src = a;
T * dest = temp;
while(未排好序）
{
    合并src中的相邻块到dest
    swap(src, dest);
}
if( src != a )
{
    复制src中所有对象到a
}

[解决办法]
我写的merge排序，代码看上去比你的多。
1亿个int排序，13.203秒，用stable_sort排序，是13.797秒

template <typename T>
void MergeSort(T arr[], int n)      //非递归的二路归并排序
{
T* temp = new T[n];             //申请一个临时数组
int i, k; 
int m1_begin, m2_begin;
int m1_end, m2_end;
T* source = arr;
T* dest = temp;

for (int step = 1; step < n ; step *= 2) //步长>=n的时候排序完成
{
k = 0;                              //辅助数组清空
for (i = 0; i < n; i += step * 2)   //每次2组数据，当第一组数据下标越界，本趟归并完成
{

merge(source, dest, n, i, step);
}                                    //一趟归并完成
temp = source;                      
source = dest;                      //用指针交换优化，效果明显
dest = temp;
}

if (source != arr)                     //最后检查arr数组是否是最终完成的数组
{
for (i = 0; i < n; i++)
arr[i] = source[i];
temp = source;
}
delete[] temp;                         //释放临时数组 
 
}

template <typename T>
void merge(T* source, T* dest, int n, int i, int step)
{
int m1_begin, m1_end, m2_begin, m2_end;
int k = i;
m1_begin = i;                 //待归并2个数组的左右边界
m1_end = i + step;
if (m1_end > n)
m1_end = n;
m2_begin = m1_end;
m2_end = m2_begin + step;
if (m2_end > n)
m2_end = n;

while (m1_begin < m1_end && m2_begin < m2_end)  //开始归并
if (source[m2_begin] < source[m1_begin])
dest[k++] = source[m2_begin++];
else
dest[k++] = source[m1_begin++];


while (m1_begin < m1_end)                     //处理剩余的一个数组
dest[k++] = source[m1_begin++];
while (m2_begin < m2_end)
dest[k++] = source[m2_begin++];

}