為什么歸并排序空間復雜度為O(N)?

個人理解空間復雜度為O(1)的歸并排序是指內(nèi)存方面的空間復雜度，而忽略了堆棧里的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;
}

歸并如果是自上而下遞歸需要壓棧,但因為歸分二分的界限是相對固定的,所以如果自下而上實現(xiàn)的話,不需要遞歸,都是數(shù)組的原位交換位置,并不需要申請額外的空間.

數(shù)組本身存儲O(N)的空間, 如果是O(1)我想可能指的是類似滑動窗口,每次只是讀取當前的需要比較的數(shù)據(jù).不過效率...

這里有原位歸并排序的論文, 可以參考下

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