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

Question

看网上说可以吧归并排序空间复杂度降到O(1)，我有个小疑问，比如说二叉树用递归实现空间复杂度即为O(logN),即为树的高度，但是归并排序递归实现不也都要把函数推入栈里面吗，再加上额外需要的数组长度N,是不是空间复杂度是O(logN+N)，所以最终是O(N)?谢谢

Answer 1

归并如果是自上而下递归需要压栈,但因为归分二分的界限是相对固定的,所以如果自下而上实现的话,不需要递归,都是数组的原位交换位置,并不需要申请额外的空间.

数组本身存储O(N)的空间, 如果是O(1)我想可能指的是类似滑动窗口,每次只是读取当前的需要比较的数据.不过效率...

这里有原位归并排序的论文, 可以参考下

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/...

Answer 2

个人理解空间复杂度为O(1)的归并排序是指内存方面的空间复杂度，而忽略了堆栈里的O(logN)的空间复杂度（毕竟不在同一个空间）

//空间复杂度为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;
}