#include <stdio.h>
#include <string.h>
# if 1
#include <stack>
#include <vector>
template<class T>
class MyStack : public std::stack<T, std::vector<T> >
{
};
#else
template<class T>
class MyStack {
union {
char* a;
T* p;
};
int n, t;
public:
explicit MyStack(int n=128) {
this->n = n;
this->t = 0;
a = new char[n*sizeof(T)];
}
~MyStack() {
while (t > 0)
pop();
delete[] a;
}
void swap(MyStack<T>& y) {
char* q = y.a; y.a = a; a = q;
int z;
z = y.n; y.n = n; n = z;
z = y.t; y.t = t; t = z;
}
T& top() const {
return p[t-1];
}
void pop() {
--t;
p[t].~T();
}
void push(const T& x) {
x.print(); // debug
p[t] = x;
++t;
}
int size() const { return t; }
bool empty() const { return 0 == t; }
bool full() const { return n == t; }
};
#endif
template<class T>
struct Frame {
static T* base;
T *beg, *tmp;
int len;
int retaddr;
Frame(T* beg, T* tmp, int len, int retaddr)
: beg(beg), tmp(tmp), len(len), retaddr(retaddr)
{}
void print() const { // for debug
printf("%4d %4d %d/n", int(beg-base), len, retaddr);
}
};
template<class T> T* Frame<T>::base;
#define TOP(field) stk.top().field
template<class T>
bool issorted(const T* a, int n)
{
for (int i = 1; i < n; ++i) {
if (a[i-1] > a[i]) return false;
}
return true;
}
template<class T>
void mymerge(const T* a, int la, const T* b, int lb, T* c) {
int i = 0, j = 0, k = 0;
for (; i < la && j < lb; ++k) {
if (b[j] < a[i])
c[k] = b[j], ++j;
else
c[k] = a[i], ++i;
}
for (; i < la; ++i, ++k) c[k] = a[i];
for (; j < lb; ++j, ++k) c[k] = b[j];
}
template<class T>
void MergeSort1(T* beg, T* tmp, int len) {
if (len > 1) {
int mid = len / 2;
MergeSort1(beg , tmp , mid);
MergeSort1(beg+mid, tmp+mid, len-mid);
mymerge(tmp, mid, tmp+mid, len-mid, beg);
memcpy(tmp, beg, sizeof(T)*len);
}
else
*tmp = *beg;
}
template<class T>
void MergeSort2(T* beg0, T* tmp0, int len0) {
int mid;
int cnt = 0;
Frame<T>::base = beg0;
MyStack<Frame<T> > stk;
stk.push(Frame<T>(beg0, tmp0, len0, 0));
while (true) {
++cnt;
if (TOP(len) > 1) {
mid = TOP(len) / 2;
stk.push(Frame<T>(TOP(beg), TOP(tmp), mid, 1));
continue;
L1:
mid = TOP(len) / 2;
stk.push(Frame<T>(TOP(beg)+mid, TOP(tmp)+mid, TOP(len)-mid, 2));
continue;
L2:
mid = TOP(len) / 2;
mymerge(TOP(tmp), mid, TOP(tmp)+mid, TOP(len)-mid, TOP(beg));
memcpy(TOP(tmp), TOP(beg), sizeof(T)*TOP(len));
} else
*TOP(tmp) = *TOP(beg);
int retaddr0 = TOP(retaddr);
stk.pop();
switch (retaddr0) {
case 0: return;
case 1: goto L1;
case 2: goto L2;
}
}
}
// This Implementation Use GCC's goto saved label value
// Very similiar with recursive version
template<class T>
void MergeSort3(T* beg0, T* tmp0, int len0) {
MyEntry:
int mid;
int retaddr;
Frame<T>::base = beg0;
MyStack<Frame<T> > stk;
stk.push(Frame<T>(beg0, tmp0, len0, 0));
#define Cat1(a,b) a##b
#define Cat(a,b) Cat1(a,b)
#define HereLabel() Cat(HereLable_, __LINE__)
#define RecursiveCall(beg, tmp, len) /
stk.push(Frame<T>(beg, tmp, len, (char*)&&HereLabel() - (char*)&&MyEntry)); /
continue; /
HereLabel():;
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// retaddr == 0 是最外层的递归调用,
// 只要到达这一层时 retaddr 才为 0,
// 此时就可以返回了
#define MyReturn /
retaddr = TOP(retaddr); /
stk.pop(); /
if (0 == retaddr) { /
return; /
} /
goto *((char*)&&MyEntry + retaddr);
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
while (true) {
if (TOP(len) > 1) {
mid = TOP(len) / 2;
RecursiveCall(TOP(beg), TOP(tmp), mid);
mid = TOP(len) / 2;
RecursiveCall(TOP(beg)+mid, TOP(tmp)+mid, TOP(len)-mid);
mid = TOP(len) / 2;
mymerge(TOP(tmp), mid, TOP(tmp)+mid, TOP(len)-mid, TOP(beg));
memcpy(TOP(tmp), TOP(beg), sizeof(T)*TOP(len));
} else
*TOP(tmp) = *TOP(beg);
MyReturn;
}
}
template<class T>
void MergeSortDriver(T* beg, int len, void (*mf)(T* beg_, T* tmp_, int len_))
{
T* tmp = new T[len];
(*mf)(beg, tmp, len);
delete[] tmp;
}
#define test(a,n,mf) /
memcpy(a, b, sizeof(a[0])*n); /
MergeSortDriver(a, n, &mf); /
printf("sort by %s:", #mf); /
for (i = 0; i < n; ++i) printf("% ld", a[i]); /
printf("/n");
int main(int argc, char* argv[])
{
int n = argc - 1;
int i;
long* a = new long[n];
long* b = new long[n];
for (i = 0; i < n; ++i)
b[i] = strtol(argv[i+1], NULL, 10);
test(a, n, MergeSort1);
test(a, n, MergeSort2);
test(a, n, MergeSort3);
printf("All Successed/n");
delete[] a;
delete[] b;
return 0;
}