原地归并排序

今天讨论的问题是Inplace Merge Sort，即原地归并排序。相比传统的归并排序，它的空间复杂度仅为

。

在原地归并排序中最主要用到了内存反转，即交换相邻的两块内存，在《编程珠玑》中又被称为手摇算法。

内存反转是这样的：给定序列

，把它变为

，要求空间为

。

分析：本问题的方法很经典，先对

反转，再对

反转，最后对

整体     进行反转，这样就得到了

。

原地归并排序原理介绍，以下面的数组为例进行说明。

开始时

分别指向这个数组的两个有序子序列的第一个值，然后

指针向后移动，直到找到比20大的值，即

移动到30，此时我们知道

指针之前的值一定是两个子序列的最小的块，先用一个临时指针

记录

的位置。然后把第二个序列的指针

向后移动，直到找到比30大的值，即

移动到55，即如下图所示：

这样，我们把

和

的内存块交换，再移动

指针，移动长度为

，得到

这样可以看出

之前的都已经排好序，而以

开始的子序列和以

开始的子序列又是开始的问题模型，同样的操作进

行下去最终排序完成。

代码：

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
const int N = 100005;

int a[N];

void swap(int a[],int x,int y)
{
    a[x] ^= a[y];
    a[y] ^= a[x];
    a[x] ^= a[y];
}

void Reverse(int a[],int x,int y)
{
    while(x < y)
        swap(a,x++,y--);
}

void Convert(int a[],int L,int M,int R)
{
    Reverse(a,L,M);
    Reverse(a,M+1,R);
    Reverse(a,L,R);
}

void Merge(int a[],int L,int M,int R)
{
    int i = L;
    int j = M + 1;
    while(i < j && j <= R)
    {
        while(i < j && a[i] <= a[j])
            i++;
        int index = j;
        while(j <= R && a[j] < a[i])
            j++;
        Convert(a,i,index-1,j-1);
        i += j - index;
    }
}

void Merge_Sort(int a[],int L,int R)
{
    if(L < R)
    {
        int M = L + (R - L) / 2;
        Merge_Sort(a,L,M);
        Merge_Sort(a,M+1,R);
        Merge(a,L,M,R);
    }
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0; i<n; i++)
            scanf("%d",&a[i]);
        Merge_Sort(a,0,n-1);
        for(int i=0; i<n; i++)
            printf("%d%c",a[i],i==n-1? '\n':' ');
    }
    return 0;
}