常用算法-归并排序

归并排序

时间复杂度：O(Nlog2N)
空间复杂度：O(N)
原理：
按照前后顺序变成完全二叉树，采用递归的方式去实现，最后将两列数字采用比较排序
核心代码：
void sort(int left,int right)
{
if(left < right)
{
int mid = (left+right)/2;
sort(left,mid);
sort(mid+1,right);
merge(left,mid,right);
}
}
void merge(int left, int mid, int right)
{
T *temp = new T[right - left + 1];
int k = 0;
int i = left;
int j = mid+1;
while(i <= mid && j <= right) temp[k++] = (list[i] < list[j]) ? list[i++] : list[j++];
while(i <= mid) temp[k++] = list[i++];
while(j <= right) temp[k++] = list[j++];
for (int n = left;n <= right;n++) {
list[n] = temp[n-left];
}
delete [] temp;
}