Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# Merge-sort

·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views
```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:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.