升序
數(shù)組
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);
}
}
