Skip to content

Instantly share code, notes, and snippets.

@gnufied
Created November 17, 2008 12:19
Show Gist options
  • Save gnufied/25738 to your computer and use it in GitHub Desktop.
Save gnufied/25738 to your computer and use it in GitHub Desktop.
#include <stdio.h>
#include <stdlib.h>
void merge(int *array,const int p, const int q,const int r) {
int n1 = q-p;
int n2 = r-q;
int *left = malloc((n1)*sizeof(int));
int *right = malloc((n2)*sizeof(int));
int i,j,k;
for(i = 0; i < n1; i++) left[i] = array[p+i];
for(i = 0; i < n2; i++) right[i] = array[q+i];
i = 0;
j = 0;
for(k = p; k < r; k++) {
if((j < n2 && i < n1 && left[i] <= right[j]) || (j >= n2 && i < n1)) {
array[k] = left[i];
i++;
} else {
if(j < n2) array[k] = right[j];
j++;
}
}
}
void merge_sort(int *array,const int p,const int r) {
if(p < r-1) {
const int q = (p+r)/2;
merge_sort(array,p,q);
merge_sort(array,q,r);
merge(array,p,q,r);
}
}
int main() {
int i;
int a[] = {10,4,67,12,12,16,9,1,4,5,11,23,13,10,14,5,4,100};
const int length = sizeof(a)/sizeof(int);
merge_sort(a,0,length);
for(i = 0 ; i < length; i++) printf("%d ",a[i]);
printf("\n");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment