Skip to content

Instantly share code, notes, and snippets.

@tomotaka
Created July 6, 2012 02:48
Show Gist options
  • Save tomotaka/3057774 to your computer and use it in GitHub Desktop.
Save tomotaka/3057774 to your computer and use it in GitHub Desktop.
merge sort by C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DATA_FILE "./rand.txt"
#define N 1000000
void my_msort(int* ary, int stack_level, int sidx, int eidx) {
int i, j, tmp;
int len = eidx - sidx + 1;
if (len <= 20 || 30 <= stack_level) {
// do bubble sort
for (i = sidx; i <= eidx; i++) {
for (j = i+1; j <= eidx; j++) {
if (ary[j] < ary[i]) {
tmp = ary[i];
ary[i] = ary[j];
ary[j] = tmp;
}
}
}
} else {
int half_len = len / 2;
int slen = half_len;
int glen = len-slen;
int s_sidx = sidx;
int s_eidx = sidx + slen - 1;
int g_sidx = sidx + slen;
int g_eidx = eidx;
my_msort(ary, stack_level+1, s_sidx, s_eidx);
my_msort(ary, stack_level+1, g_sidx, g_eidx);
int* smallers = (int*)malloc(sizeof(int)*slen);
int* greaters = (int*)malloc(sizeof(int)*glen);
memcpy(smallers, ary+s_sidx, sizeof(int)*slen);
memcpy(greaters, ary+g_sidx, sizeof(int)*glen);
// merge
i = sidx;
int si = 0, gi = 0;
while (i <= eidx) {
if (si < slen) {
if (gi < glen) {
if (smallers[si] < greaters[gi]) {
ary[i++] = smallers[si++];
} else {
ary[i++] = greaters[gi++];
}
} else {
ary[i++] = smallers[si++];
}
} else if (gi < glen) {
ary[i++] = greaters[gi++];
}
}
free(smallers);
free(greaters);
}
}
int main(int argc, char** argv) {
int i;
int* vec;
char buf[128];
FILE* fp = fopen(DATA_FILE, "r");
vec = (int*)malloc(sizeof(int) * N);
for (i = 0; i < N; i++) {
fgets(buf, 128, fp);
vec[i] = atoi(buf);
}
fclose(fp);
//my_qsort(vec, 1, 0, N-1);
my_msort(vec, 1, 0, N-1);
for (i = 0; i < N; i++) {
printf("%d\n", vec[i]);
}
free(vec);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment