Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void SplitMergeAtoA(int a[], int b[], size_t ll, size_t ee);
void SplitMergeAtoB(int a[], int b[], size_t ll, size_t ee);
void Merge(int a[], int b[], size_t ll, size_t rr, size_t ee);
void MergeSort(int a[], size_t n) // entry function
{
int *b;
if(n < 2) // if size < 2 return
return;
b = malloc(n*sizeof(int));
SplitMergeAtoA(a, b, 0, n);
free(b);
}
void SplitMergeAtoA(int a[], int b[], size_t ll, size_t ee)
{
size_t rr;
if((ee - ll) == 1) // if size == 1 return
return;
rr = (ll + ee)>>1; // midpoint, start of right half
SplitMergeAtoB(a, b, ll, rr);
SplitMergeAtoB(a, b, rr, ee);
Merge(b, a, ll, rr, ee); // merge b to a
}
void SplitMergeAtoB(int a[], int b[], size_t ll, size_t ee)
{
size_t rr;
if((ee - ll) == 1){ // if size == 1 copy a to b
b[ll] = a[ll];
return;
}
rr = (ll + ee)>>1; // midpoint, start of right half
SplitMergeAtoA(a, b, ll, rr);
SplitMergeAtoA(a, b, rr, ee);
Merge(a, b, ll, rr, ee); // merge a to b
}
void Merge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
size_t o = ll; // b[] index
size_t l = ll; // a[] left index
size_t r = rr; // a[] right index
while(1){ // merge data
if(a[l] <= a[r]){ // if a[l] <= a[r]
b[o++] = a[l++]; // copy a[l]
if(l < rr) // if not end of left run
continue; // continue (back to while)
while(r < ee) // else copy rest of right run
b[o++] = a[r++];
break; // and return
} else { // else a[l] > a[r]
b[o++] = a[r++]; // copy a[r]
if(r < ee) // if not end of right run
continue; // continue (back to while)
while(l < rr) // else copy rest of left run
b[o++] = a[l++];
break; // and return
}
}
}
#define N (16*1024*1024)
int main(void){
int *a = malloc(N * sizeof(int));
int i;
clock_t ctTimeStart; // clock values
clock_t ctTimeStop;
for(i = 0; i < N; i++)
a[i] = rand();
ctTimeStart = clock();
MergeSort(a, N);
ctTimeStop = clock();
for(i = 1; i < N; i++){ // check for error
if(a[i-1] > a[i]){
printf("sort failed\n");
break;
}
}
if(i == N){
printf("sort passed\n");
printf("# of ticks %d\n", ctTimeStop-ctTimeStart);
}
free(a);
return 0;
}