Merge-sort

• Tweet
• 

        Implements the classic Merge-sort algorithm.

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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;
}

Tags:
• algorithm
• C
• merge-sort
• sort