個(gè)人理解空間復(fù)雜度為O(1)的歸并排序是指內(nèi)存方面的空間復(fù)雜度，而忽略了堆棧里的O(logN)的空間復(fù)雜度（畢竟不在同一個(gè)空間）

//空間復(fù)雜度為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;
}

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

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

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

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