#include <stdio.h>
#include <stdlib.h>
#include <time.h>
enum{N=10};
void merge(int *array, int links, int mitte, int rechts)
{
int i, j, k;
int n1 = mitte - links + 1;
int n2 = rechts - mitte;
int *temp_array, *temp_array2;
temp_array
= malloc(sizeof(*temp_array
) * n1
); temp_array2
= malloc(sizeof(*temp_array2
) * n2
); if(temp_array == NULL || temp_array2 == NULL)
{
printf("Fehler bei der Speicher reservierung!"); }
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
{
temp_array[i] = array[links + i];
//printf("temp1 = %d",temp_array[i]);
}
for (j = 0; j < n2; j++)
{
temp_array2[j] = array[mitte + 1 + j];
}
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = links; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (temp_array[i] <= temp_array2[j])
{
array[k] = temp_array[i];
i++;
}
else
{
array[k] = temp_array2[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
array[k] = temp_array[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
array[k] = temp_array2[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int *array, int links, int rechts)
{
if (links < rechts)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int mitte = links+(rechts-links)/2;
// Sort first and second halves
mergeSort(array, links, mitte);
mergeSort(array, mitte+1, rechts);
merge(array, links, mitte, rechts);
}
//printArray(array, n);
}
/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int *A, int size)
{
int i;
for (i=0; i < size; i++)
{
}
}
/* Driver program to test above functions */
int main()
{
int i;
int *arr
= calloc(N
,sizeof*arr
);
for(i = 0; i < N; i++)
{
}
printArray(arr, N);
mergeSort(arr, 0, N - 1);
printArray(arr, N);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHRpbWUuaD4KCmVudW17Tj0xMH07Cgp2b2lkIG1lcmdlKGludCAqYXJyYXksIGludCBsaW5rcywgaW50IG1pdHRlLCBpbnQgcmVjaHRzKSAKeyAKICAgaW50IGksIGosIGs7IAogICBpbnQgbjEgPSBtaXR0ZSAtIGxpbmtzICsgMTsgCiAgIGludCBuMiA9ICByZWNodHMgLSBtaXR0ZTsgCiAKICAgaW50ICp0ZW1wX2FycmF5LCAqdGVtcF9hcnJheTI7IAogICB0ZW1wX2FycmF5ID0gbWFsbG9jKHNpemVvZigqdGVtcF9hcnJheSkgKiBuMSk7CiAgIHRlbXBfYXJyYXkyID0gbWFsbG9jKHNpemVvZigqdGVtcF9hcnJheTIpICogbjIpOwogCWlmKHRlbXBfYXJyYXkgPT0gTlVMTCB8fCB0ZW1wX2FycmF5MiA9PSBOVUxMKQogCXsKIAkJcHJpbnRmKCJGZWhsZXIgYmVpIGRlciBTcGVpY2hlciByZXNlcnZpZXJ1bmchIik7CiAgIAlleGl0KDEpOyAgCQogICB9CiAJCiAgIC8qIENvcHkgZGF0YSB0byB0ZW1wIGFycmF5cyBMW10gYW5kIFJbXSAqLwogICBmb3IgKGkgPSAwOyBpIDwgbjE7IGkrKykgCiAgIHsKICAgCXRlbXBfYXJyYXlbaV0gPSBhcnJheVtsaW5rcyArIGldOyAKICAgCS8vcHJpbnRmKCJ0ZW1wMSA9ICVkIix0ZW1wX2FycmF5W2ldKTsKICAgfQogICAgICAgCiAgIGZvciAoaiA9IDA7IGogPCBuMjsgaisrKSAKICAgewogICAJdGVtcF9hcnJheTJbal0gPSBhcnJheVttaXR0ZSArIDEgKyBqXTsgCiAgIH0KICAgICAgIAogCiAgIC8qIE1lcmdlIHRoZSB0ZW1wIGFycmF5cyBiYWNrIGludG8gYXJyW2wuLnJdKi8KICAgaSA9IDA7IC8vIEluaXRpYWwgaW5kZXggb2YgZmlyc3Qgc3ViYXJyYXkgCiAgIGogPSAwOyAvLyBJbml0aWFsIGluZGV4IG9mIHNlY29uZCBzdWJhcnJheSAKICAgayA9IGxpbmtzOyAvLyBJbml0aWFsIGluZGV4IG9mIG1lcmdlZCBzdWJhcnJheSAKICAgd2hpbGUgKGkgPCBuMSAmJiBqIDwgbjIpIAogICB7IAogICAgICAgaWYgKHRlbXBfYXJyYXlbaV0gPD0gdGVtcF9hcnJheTJbal0pIAogICAgICAgeyAKICAgICAgICAgICBhcnJheVtrXSA9IHRlbXBfYXJyYXlbaV07IAogICAgICAgICAgIGkrKzsgCiAgICAgICB9IAogICAgICAgZWxzZQogICAgICAgeyAKICAgICAgICAgICBhcnJheVtrXSA9IHRlbXBfYXJyYXkyW2pdOyAKICAgICAgICAgICBqKys7IAogICAgICAgfSAKICAgICAgIGsrKzsgCiAgIH0gCiAKICAgLyogQ29weSB0aGUgcmVtYWluaW5nIGVsZW1lbnRzIG9mIExbXSwgaWYgdGhlcmUgCiAgICAgIGFyZSBhbnkgKi8KICAgd2hpbGUgKGkgPCBuMSkgCiAgIHsgCiAgICAgICBhcnJheVtrXSA9IHRlbXBfYXJyYXlbaV07IAogICAgICAgaSsrOyAKICAgICAgIGsrKzsgCiAgIH0gCiAKICAgLyogQ29weSB0aGUgcmVtYWluaW5nIGVsZW1lbnRzIG9mIFJbXSwgaWYgdGhlcmUgCiAgICAgIGFyZSBhbnkgKi8KICAgd2hpbGUgKGogPCBuMikgCiAgIHsgCiAgICAgICBhcnJheVtrXSA9IHRlbXBfYXJyYXkyW2pdOyAKICAgICAgIGorKzsgCiAgICAgICBrKys7IAogICB9IAogICAKICAgZnJlZSh0ZW1wX2FycmF5Mik7ZnJlZSh0ZW1wX2FycmF5KTsKfSAKIAovKiBsIGlzIGZvciBsZWZ0IGluZGV4IGFuZCByIGlzIHJpZ2h0IGluZGV4IG9mIHRoZSAKICBzdWItYXJyYXkgb2YgYXJyIHRvIGJlIHNvcnRlZCAqLwp2b2lkIG1lcmdlU29ydChpbnQgKmFycmF5LCBpbnQgbGlua3MsIGludCByZWNodHMpIAp7IAogICBpZiAobGlua3MgPCByZWNodHMpIAogICB7IAogICAgICAgLy8gU2FtZSBhcyAobCtyKS8yLCBidXQgYXZvaWRzIG92ZXJmbG93IGZvciAKICAgICAgIC8vIGxhcmdlIGwgYW5kIGggCiAgICAgICBpbnQgbWl0dGUgPSBsaW5rcysocmVjaHRzLWxpbmtzKS8yOyAKIAogICAgICAgLy8gU29ydCBmaXJzdCBhbmQgc2Vjb25kIGhhbHZlcyAKICAgICAgIG1lcmdlU29ydChhcnJheSwgbGlua3MsIG1pdHRlKTsgCiAgICAgICBtZXJnZVNvcnQoYXJyYXksIG1pdHRlKzEsIHJlY2h0cyk7IAogCiAgICAgICBtZXJnZShhcnJheSwgbGlua3MsIG1pdHRlLCByZWNodHMpOyAKICAgfSAKICAgLy9wcmludEFycmF5KGFycmF5LCBuKTsgCn0gCiAKLyogVVRJTElUWSBGVU5DVElPTlMgKi8KLyogRnVuY3Rpb24gdG8gcHJpbnQgYW4gYXJyYXkgKi8Kdm9pZCBwcmludEFycmF5KGludCAqQSwgaW50IHNpemUpIAp7IAogICBpbnQgaTsgCiAgIGZvciAoaT0wOyBpIDwgc2l6ZTsgaSsrKSAKICAgewogICAJcHJpbnRmKCIlZCAiLCBBW2ldKTsgCiAgIH0KICAgcHJpbnRmKCJcbiIpOyAKfSAKIAovKiBEcml2ZXIgcHJvZ3JhbSB0byB0ZXN0IGFib3ZlIGZ1bmN0aW9ucyAqLwppbnQgbWFpbigpIAp7IAogCWludCBpOwogCWludCAqYXJyID0gY2FsbG9jKE4sc2l6ZW9mKmFycik7CiAJc3JhbmQodGltZShOVUxMKSk7CiAJCiAJZm9yKGkgPSAwOyBpIDwgTjsgaSsrKQogCXsKIAkgICAgYXJyW2ldID0gcmFuZCgpICUgMTAwOwogICAgfQogCQogICBwcmludEFycmF5KGFyciwgTik7IAogCiAgIG1lcmdlU29ydChhcnIsIDAsIE4gLSAxKTsgCgogICBwcmludEFycmF5KGFyciwgTik7IAogICAKICAgZnJlZShhcnIpOwogICAKICAgcmV0dXJuIDA7IAp9IAoK