## Merge Sort Back

• 歸併排序: 分治思想(Divide, Conquer and Combination)
• Divide: 二分
• Conquer: 直到只有一個的時候合併
• Combination: 每次比較隊頭,較小的先放進隊列
• 时间复杂度: (最好,平均,最壞情況)
• 空間複雜度:
• 稳定性: 稳定
• 适用情况: 額外空間可以接受的情況下
``````void Merge(int A[], int p, int m, int q)
{
int n1 = m - p + 1;
int n2 = q - (m + 1) + 1;
int L[MAXSIZE], R[MAXSIZE];
for (int i = 1; i <= n1; i++)
{
L[i] = A[p + i - 1];
}
for (int j = 1; j <= n2; j++)
{
R[j] = A[m + j];
}
L[n1 + 1] = INFINITY;
R[n2 + 1] = INFINITY;
int i = 1;
int j = 1;
for (int k = p; k <= q; k++)
{
if (L[i] <= R[j])
{
A[k] = L[i];
i++;
}
else
{
A[k] = R[j];
j++;
}
}
}

void MergeSort(int A[], int p, int q)
{
if (p < q)
{
int m = (p + q) / 2;
MergeSort(A, p, m);
MergeSort(A, m + 1, q);
Merge(A, p, m, q);
}
}
``````
Empty Comments
Sign in GitHub

As the plugin is integrated with a code management system like GitLab or GitHub, you may have to auth with your account before leaving comments around this article.

Notice: This plugin has used Cookie to store your token with an expiration.