# 为什么归并排序空间复杂度为O(N)?

ZHONGJIAFENG7
• 165

##### 2个回答

It is shown that an array of n elements can be sorted using O(1) extra space,
O(n log n= log log n) element moves, and n log2 n + O(n log log n) comparisons. This
is the rst in-place sorting algorithm requiring o(n log n) moves in the worst case
while guaranteeing O(n log n) comparisons but, due to the constant factors involved,
the algorithm is predominantly of theoretical interest.

http://citeseerx.ist.psu.edu/...

``````//空间复杂度为O(1)的归并排序
#include <iostream>
using namespace std;

void reverse_array(int a[], int n) {
int i = 0;
int j = n - 1;
while (i < j) {
swap(a[i], a[j]);
++i;
--j;
}
}

void exchange(int a[], int length, int length_left) {
reverse_array(a, length_left);
reverse_array(a + length_left, length - length_left);
reverse_array(a, length);
}

void Merge(int a[], int begin, int mid, int end) {
while (begin < mid && mid <= end) {
int step = 0;
while (begin < mid && a[begin] <= a[mid])
++begin;
while (mid <= end && a[mid] <= a[begin]) {
++mid;
++step;
}
exchange(a + begin, mid - begin, mid - begin - step);
}
}

void MergeCore(int a[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
MergeCore(a, left, mid);
MergeCore(a, mid + 1, right);
Merge(a, left, mid + 1, right);
}
}

void MergeSort(int a[], int length) {
if (a == NULL || length < 1)
return;
MergeCore(a, 0, length - 1);
}

int main() {
int a[] = {1,0,2,9,3,8,4,7,6,5,11,99,22,88,11};
int length = sizeof(a) / sizeof(int);
MergeSort(a, length);

for (int i = 0; i < length; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}``````
##### 撰写回答
###### 你尚未登录，登录后可以
• 和开发者交流问题的细节
• 关注并接收问题和回答的更新提醒
• 参与内容的编辑和改进，让解决方法与时俱进