```// ************************************************************************** //
//                                                                            //
//    eses                   eses                                             //
//   eses                     eses                                            //
//  eses    eseses  esesese    eses   Embedded Systems Group                  //
//  ese    ese  ese ese         ese                                           //
//  ese    eseseses eseseses    ese   Department of Computer Science          //
//  eses   eses          ese   eses                                           //
//   eses   eseses  eseseses  eses    University of Kaiserslautern            //
//    eses                   eses                                             //
//                                                                            //
// ************************************************************************** //
// MergeSort is one of the most efficient sorting algorithms, not only because//
// of its optimal best, average and worst case asymptotic complexity of only  //
// O(n*log(n)), but also due to practical runtimes. The version given below   //
// in Quartz performs a simple in-place merge, which is possible due to the   //
// concurrency available in Quartz.                                           //
// MergeSort is a divide-and-conquer algorithm that splits the list into      //
// halves, sorts them, and merges the sorted lists into a sorted list. The    //
// main problem is thereby to implement the merging efficiently. For a list   //
// of length n, log(n) merging phases are required in sequence, and in each   //
// phase the entire list, partitioned into sorted sequences, is merged into   //
// larger sorted partitions.                                                  //
// ************************************************************************** //

macro aSize = 16;
macro iSize = 64;

module MergeSort([aSize+1]int{iSize} ?a,b, event !ready) {
[aSize]int{iSize} c;
nat{aSize+1} i0,i1,j0,j1,j,l;
l = 2;

// initial swaps to achieve sorted partitions of length 2
for(i=0..aSize/2-1)
if(a[2*i] > a[2*i+1]) {
next(b[2*i]) = a[2*i+1];
next(b[2*i+1]) = a[2*i];
} else {
next(b[2*i]) = a[2*i];
next(b[2*i+1]) = a[2*i+1];
}
w0: pause;

// perform log(aSize) merging phases; l denotes the length of the sorted partitions
// in each of these phases
l = 2;
while(l<=aSize/2) {
// merging partitions of length l into array c
i0 = 0; // current position in left  partition
i1 = 0; // current position in right partition
j  = 0; // position of c to write next
j0 = 0; // start of current left  partition
j1 = l; // start of current right partition
while(j0+l<aSize) {
// merge sorted sequences b[j0..j0+l-1] with b[j1..j1+l-1] into c[j0..j1+l-1]
while(i0<l & i1<l) {
if(b[i0+j0] > b[i1+j1]) {
next(c[j]) = b[i1+j1];
next(i1) = i1+1;
next(j) = j+1;
} else {
next(c[j]) = b[i0+j0];
next(i0) = i0+1;
next(j) = j+1;
}
w1: pause;
}
// copy the rest of b[j0..j0+l-1] to c
while(i0<l) {
next(c[j]) = b[i0+j0];
next(i0) = i0+1;
next(j) = j+1;
w2: pause;
}
// copy the rest of b[j1..j1+l-1] to c
while(i1<l) {
next(c[j]) = b[i1+j1];
next(i1) = i1+1;
next(j) = j+1;
w3: pause;
}
// prepare indices for merging the next partition
next(i0) = 0;
next(i1) = 0;
next(j0) = sat{aSize}(j0+l+l);
next(j1) = sat{aSize}(j1+l+l);
w4: pause;
}
// all partitions of size l are merged, thus copy c back to b
for(i=0..aSize-1)
b[i] = c[i];
next(l) = l+l;
w5: pause;
}

}
drivenby Test01 {
for(i=0..aSize-1) a[i] = i;
for(i=0..aSize-1) assert(b[i] == i);
}
drivenby Test02 {
for(i=0..aSize-1) a[i] = aSize-1-i;