原地二路归并

原地二路归并排序。

codepad.org已验证。

Reference:

http://www.cppblog.com/converse/archive/2008/09/28/63008.html

#include <stdio.h>
#include <stdlib.h>
#define SWAP(a,b) (a)^=b;(b)^=a;(a)^=b;
void output(int*input, int size){
        int i = 0;
    for(;i<size;i++){
        printf("%d->",input[i]);
    }
    printf("\n");
}
void rev(int *input, int start, int end){
    if(input == NULL || start>=end) return;
    while(start<end){
        SWAP(input[start],input[end]);
        start++;
        end--;
    }
}
void rotate(int *input, int start, int end, int piv){
    if(input == NULL || start>=end || piv>end || piv<start) return;
    rev(input, start, end);
    rev(input,start,start+end-piv);
    rev(input,start+end-piv+1, end);
}

void merge(int *input, int start, int end, int mid){
    if(input == NULL || start >= end) return;
    int left = start;
    int right = mid+1;
    while(left<=end && right<=end){
        if(input[left]>input[right]){
            rotate(input, left,right,right);
            left++;
            right++;
        }
        else
            left++;
    }

}

void mergesort(int *input, int start, int end){
    if(input == NULL || end<=start) return;
    int mid = (start+end)>>1;

    mergesort(input, start, mid);
    mergesort(input, mid+1, end);

    merge(input, start, end, mid);
}

int main(){
    int input[] = {1,3,5,7,8,4,3,2};
    mergesort(input, 0, sizeof(input)/sizeof(int)-1);
    int i = 0;
    output(input, 8);

}