下面程序的 Merge_Sort 函数时间复杂度为（ ）。
void Merge(int a[], int left, int mid, int right) {
int temp[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (a[i] < a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= mid)
temp[k++] = a[i++];
while (j <= right)
temp[k++] = a[j++];
for (int m = left, n = 0; m <= right; m++, n++)
a[m] = temp[n];
}
void Merge_Sort(int a[], int left, int right) {
if (left == right)
return;
int mid = (left + right) / 2;
Merge_Sort(a, left, mid);
Merge_Sort(a, mid + 1, right);
Merge(a, left, mid, right);
}
O(n log n)
O(n2)
O(2n)
O(log n)