Articles

归并排序(Merge Sort)

归并排序是一种递归的排序方式,它将待排序的数组分成左右两部分,分别进行归并排序。这样一直划分下去,直到待排序的元素只有一个,那这个元素自然是已经排好序的了。然后,再将排好序的左半部分与右半部分归并(merge)。该算法的核心也正是这个归并的操作。

如图所示,由于归并排序使用了递归,形成了一个深度是\( O(lgn) \)的二叉树,每一层对左右两部分进行归并的操作时间复杂度是\( O(n) \),因此,该排序算法的时间复杂度是\( O(nlgn) \)。空间上,最终一次归并操作所需的内存最多,所以空间复杂度是\( O(n) \)。

template <typename T>
void merge(T a[], int low, int middle, int high)
{
    // a[low, ..., middle] -> lhs[0, ..., middle - low + 1]
    // a[middle + 1, ..., high] -> rhs[0, ..., high - middle]
    int nl = middle - low + 1;
    int nr = high - middle;

    T *lhs = new T[nl];
    T *rhs = new T[nr];

    for (int i = 0; i < nl; i++)
        lhs[i] = a[low + i];

    for (int j = 0; j < nr; j++)
        rhs[j] = a[middle + 1 + j];

    // merge
    int i = 0, j = 0, k = 0;
    while (i < nl && j < nr)
        if (lhs[i] < rhs[j])
        {
            a[low + k++] = lhs[i++];
        } else {
            a[low + k++] = rhs[j++];
        }

    while (i < nl)
        a[low + k++] = lhs[i++];
    while (j < nr)
        a[low + k++] = rhs[j++];

    delete [] lhs;
    delete [] rhs;
}

template <typename T>
void merge_sort(T a[], int low, int high)
{
    if (low < high)
    {
        int middle = (low + high) / 2;
        merge_sort(a, low, middle);
        merge_sort(a, middle + 1, high);
        merge(a, low, middle, high);
    }
}