fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. enum{N=10};
  6.  
  7. void merge(int *array, int links, int mitte, int rechts) 
  8. { 
  9.    int i, j, k; 
  10.    int n1 = mitte - links + 1; 
  11.    int n2 =  rechts - mitte; 
  12.  
  13.    int *temp_array, *temp_array2; 
  14.    temp_array = malloc(sizeof(*temp_array) * n1);
  15.    temp_array2 = malloc(sizeof(*temp_array2) * n2);
  16.  	if(temp_array == NULL || temp_array2 == NULL)
  17.  	{
  18.  		printf("Fehler bei der Speicher reservierung!");
  19.    	exit(1);  	
  20.    }
  21.  
  22.    /* Copy data to temp arrays L[] and R[] */
  23.    for (i = 0; i < n1; i++) 
  24.    {
  25.    	temp_array[i] = array[links + i]; 
  26.    	//printf("temp1 = %d",temp_array[i]);
  27.    }
  28.  
  29.    for (j = 0; j < n2; j++) 
  30.    {
  31.    	temp_array2[j] = array[mitte + 1 + j]; 
  32.    }
  33.  
  34.  
  35.    /* Merge the temp arrays back into arr[l..r]*/
  36.    i = 0; // Initial index of first subarray 
  37.    j = 0; // Initial index of second subarray 
  38.    k = links; // Initial index of merged subarray 
  39.    while (i < n1 && j < n2) 
  40.    { 
  41.        if (temp_array[i] <= temp_array2[j]) 
  42.        { 
  43.            array[k] = temp_array[i]; 
  44.            i++; 
  45.        } 
  46.        else
  47.        { 
  48.            array[k] = temp_array2[j]; 
  49.            j++; 
  50.        } 
  51.        k++; 
  52.    } 
  53.  
  54.    /* Copy the remaining elements of L[], if there 
  55.       are any */
  56.    while (i < n1) 
  57.    { 
  58.        array[k] = temp_array[i]; 
  59.        i++; 
  60.        k++; 
  61.    } 
  62.  
  63.    /* Copy the remaining elements of R[], if there 
  64.       are any */
  65.    while (j < n2) 
  66.    { 
  67.        array[k] = temp_array2[j]; 
  68.        j++; 
  69.        k++; 
  70.    } 
  71.  
  72.    free(temp_array2);free(temp_array);
  73. } 
  74.  
  75. /* l is for left index and r is right index of the 
  76.   sub-array of arr to be sorted */
  77. void mergeSort(int *array, int links, int rechts) 
  78. { 
  79.    if (links < rechts) 
  80.    { 
  81.        // Same as (l+r)/2, but avoids overflow for 
  82.        // large l and h 
  83.        int mitte = links+(rechts-links)/2; 
  84.  
  85.        // Sort first and second halves 
  86.        mergeSort(array, links, mitte); 
  87.        mergeSort(array, mitte+1, rechts); 
  88.  
  89.        merge(array, links, mitte, rechts); 
  90.    } 
  91.    //printArray(array, n); 
  92. } 
  93.  
  94. /* UTILITY FUNCTIONS */
  95. /* Function to print an array */
  96. void printArray(int *A, int size) 
  97. { 
  98.    int i; 
  99.    for (i=0; i < size; i++) 
  100.    {
  101.    	printf("%d ", A[i]); 
  102.    }
  103.    printf("\n"); 
  104. } 
  105.  
  106. /* Driver program to test above functions */
  107. int main() 
  108. { 
  109.  	int i;
  110.  	int *arr = calloc(N,sizeof*arr);
  111.  	srand(time(NULL));
  112.  
  113.  	for(i = 0; i < N; i++)
  114.  	{
  115.  	    arr[i] = rand() % 100;
  116.     }
  117.  
  118.    printArray(arr, N); 
  119.  
  120.    mergeSort(arr, 0, N - 1); 
  121.  
  122.    printArray(arr, N); 
  123.  
  124.    free(arr);
  125.  
  126.    return 0; 
  127. } 
  128.  
  129.  
Success #stdin #stdout 0s 9424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
15 1 48 83 55 84 48 85 53 79 
1 15 48 48 53 55 79 83 84 85
https://ideone.com/djk19b
language:
C (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!