归并排序

思想

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

算法描述

void _MergeSection(int* a, int* tmp, int left1, int right1, int left2, int right2)
{
    int first1 = left1;
    int first2 = left2;
    int last1 = right1;
    int last2 = right2;

    int index = 0;
    while (first1 <= last1 && first2 <= last2)
    {
        if (a[first1] >= a[first2])
        {
            tmp[index++] = a[first2++];
        }
        else
            tmp[index++] = a[first1++];
    }
    while (first1 <= last1)
    {
        tmp[index++] = a[first1++];
    }
    while (first2 <= last2)
    {
        tmp[index++] = a[first2++];
    }

    for (int i = 0; i < index; ++i)
    {
        a[left1 + i] = tmp[i];
    }
}

void _MergeSort(int* a, int* tmp, int left, int right)
{
    assert(tmp);
    if (left < right)
    {
        int mid = left + (right - left) / 2;
        _MergeSort(a, tmp, left, mid);
        _MergeSort(a, tmp, mid + 1, right);
        _MergeSection(a, tmp, left, mid, mid + 1, right);
    }
}

//[]
void MergeSort(int* a, size_t size)
{
    assert(a);
    //tmp的作用，保存a,便于操作
    int* tmp = new int[size];
    _MergeSort(a, tmp, 0, size - 1);
    delete tmp;
}

复杂度

时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。
空间复杂度为 O(n)
比较操作的次数介于(nlogn) / 2和nlogn - n + 1。
赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0 (n)
归并排序比较占用内存，但却是一种效率高且稳定的算法。