【数据结构】归并排序！！！

归并排序
整体思想：将数据分成很多的部分，每次排序数据的一部分，然后将两部分的数据进行整体排序，这样一步一步将整体数据排序。
如图：

注：将需要排序的数据进行分块，当每个块的数据足够的少的时候就可以进行效率高的排序方法，当两块数据排序好的时候就可以将两块排序好的数据进行合并。
具体实现方法：

#ifndef _MERGESORT_H
#define _MERGESORT_H
#include<iostream>
using namespace std;


template<class T>
void merge(T* arr,size_t start,size_t end,T* tmp){
    size_t left_length = (end - start +1)/2 + 1;
    size_t mid = start + left_length;
    size_t result_length = start;
    size_t right = mid;
    size_t left = start;
while(left < mid && right <= end){
if(arr[left] <= arr[right])
            tmp[result_length++] = arr[left++];
else   
            tmp[result_length++] = arr[right++];
    }
while(left < mid){
        tmp[result_length++] = arr[left++];
    }
while(right <= end){
        tmp[result_length++] = arr[right++];
    }
}


template<class T>
void _mergesort(T* arr,size_t start,size_t end,T* tmp){
if(NULL == arr)
        return ;
    size_t mid = (end-start+1)/2+start;
if(end - start == 1){
if(arr[start] > arr[end])
            swap(arr[start],arr[end]);
        return ;
    }
else if(end - start == 0){
        return ;
    }
else{
        _mergesort(arr,start,mid,tmp);
        _mergesort(arr,mid+1,end,tmp);
        merge(arr,start,end,tmp);
for(size_t i = start;i <= end;i++)
            arr[i] = tmp[i];
    }
}
template<class T>
void mergesort(T* arr,size_t size){
if(NULL == arr)
        return;
    T* tmp = new T[sizeof(T)*size];
    _mergesort(arr,0,size,tmp);
    delete[] tmp;
}

#endif