归并排序

归并排序
//归并merge,需要一个辅助数组

void merge(vector<int>&arr, int start, int mid, int end, vector<int>&temp)
{
    int istart = start;
    int iend = mid;
    int jstart = mid + 1;
    int jend = end;
    while (istart <=iend&& jstart<=jend)
    {
        if (arr[istart] > arr[jstart])
        {
            temp.push_back(arr[jstart]);
            jstart++;
        }
        else
        {
            temp.push_back(arr[istart]);
            istart++;
        }
    }
    while (istart <= iend)
    {
            temp.push_back(arr[istart]);
            istart++;
    }
    while (jstart <= jend)
    {
        temp.push_back(arr[jstart]);
        jstart++;
    }
    for (int i = 0; i < temp.size(); i++)
    {
        arr[start + i] = temp[i];
    }
    temp.clear();
}
void mergeSort(vector<int>&arr, int start, int end, vector<int>&temp)
{
    if (start < end)
    {
        int mid = (start + end) / 2;
        mergeSort(arr, start, mid, temp);
        mergeSort(arr, mid + 1, end, temp);
        merge(arr, start, mid, end, temp);
    }
}