Over a million developers have joined DZone.

Merge-sort

·
Implements the classic Merge-sort algorithm.

Time: theta(lg(n))
Space: theta(n)


#include 
#include 
#include 

void printv(char* in, int *v, int n) {
	printf("%s", in);
	int i = 0;
	for (; i < n; ++i)
		printf("%d ", v[i]);
	printf("\n");
}

void merge(int *v, int p, int q, int r) {
	int i = p;
	int j = q + 1;
	
	int *tmp = (int*)malloc((r - p + 1) * sizeof(int));
	int k = 0;
	
	while ((i <= q) && (j <= r)) {
		if (v[i] < v[j])
			tmp[k++] = v[i++];
		else
			tmp[k++] = v[j++];
	}
	
	while (i <= q)
		tmp[k++] = v[i++];
	
	while (j <= r)
		tmp[k++] = v[j++];
	
	memcpy(v + p, tmp, (r - p + 1) * sizeof(int));
	free(tmp);
}

void mergeS(int *v, int p, int r) {
	if (p < r) {
		int q = (p + r) / 2;
		mergeS(v, p, q);
		mergeS(v, q + 1, r);
		merge(v, p, q, r);
	}
}

int main(int argc, char *argv[]) {
	int n = 10;
	int v[] = {9, 8, 7, 6, 5, 5, 4, 3, 2, 1};
	
	printv("V: ", v, n);
	mergeS(v, 0, n - 1);
	printv("V: ", v, n);
	
	return 0;
}
Topics:

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}