升序

数组

void merge(int* ar, int p, int q, int r)
{
    if (q >= p && q <= r)
    {
        int n1 = q - p + 1;
        int n2 = r - q;
        int* left = new int[n1];
        int* right = new int[n2];
        for (int i = 0; i < n1; i++)
            left[i] = ar[p + i];
        for (int i = 0; i < n2; i++)
            right[i] = ar[q + i + 1];
        int i = 0, j = 0;
        while (i < n1 && j < n2)
        {
            if (left[i] < right[j])
            {
                ar[p + i + j] = left[i];
                i++;
            }
            else
            {
                ar[p + i + j] = right[j];
                j++;
            }
        }
        while (i < n1)
        {
            ar[p + i + j] = left[i];
            i++;
        }
        while (j < n2)
        {
            ar[p + i + j] = right[j];
            i++;
        }
    }
}
void merge_sort(int* ar, int p, int r)
{
    if (p < r)
    {
        int q = (p + r) / 2;
        merge_sort(ar, p, q);
        merge_sort(ar, q, r);
        merge(ar, p, q, r);
    }
}