fork download
copy 
  1. #include <stdio.h>
  2.  
  3. void merge(int arr[], int l, int m, int r)
  4. {
  5.     int i, j, k;
  6.     int n1 = m - l + 1;
  7.     int n2 =  r - m;
  8.  
  9.     /* create temp arrays */
  10.     int L[n1], R[n2];
  11.  
  12.     /* Copy data to temp arrays L[] and R[] */
  13.     for (i = 0; i < n1; i++)
  14.         L[i] = arr[l + i];
  15.     for (j = 0; j < n2; j++)
  16.         R[j] = arr[m + 1+ j];
  17.  
  18.     /* Merge the temp arrays back into arr[l..r]*/
  19.     i = 0; // Initial index of first subarray
  20.     j = 0; // Initial index of second subarray
  21.     k = l; // Initial index of merged subarray
  22.     while (i < n1 && j < n2)
  23.     {
  24.         if (L[i] <= R[j])
  25.         {
  26.             arr[k] = L[i];
  27.             i++;
  28.         }
  29.         else
  30.         {
  31.             arr[k] = R[j];
  32.             j++;
  33.         }
  34.         k++;
  35.     }
  36.  
  37.     /* Copy the remaining elements of L[], if there
  38.        are any */
  39.     while (i < n1)
  40.     {
  41.         arr[k] = L[i];
  42.         i++;
  43.         k++;
  44.     }
  45.  
  46.     /* Copy the remaining elements of R[], if there
  47.        are any */
  48.     while (j < n2)
  49.     {
  50.         arr[k] = R[j];
  51.         j++;
  52.         k++;
  53.     }
  54. }
  55.  
  56. /* l is for left index and r is right index of the
  57.    sub-array of arr to be sorted */
  58. void mergeSort(int arr[], int l, int r)
  59. {
  60.     if (l < r)
  61.     {
  62.         // Same as (l+r)/2, but avoids overflow for
  63.         // large l and h
  64.         int m = l+(r-l)/2;
  65.  
  66.         // Sort first and second halves
  67.         mergeSort(arr, l, m);
  68.         mergeSort(arr, m+1, r);
  69.  
  70.         merge(arr, l, m, r);
  71.     }
  72. }
  73.  
  74. void print(int *A, int n) {
  75.     printf("[");
  76.     for(int i = 0; i < n; i++) {
  77.         printf(" %i ", A[i]);
  78.     }
  79.     printf("]");
  80.     printf("\n\n");
  81. }
  82.  
  83. int main(void) {
  84.     int A[] = {1,7,3,8,5,2,9};
  85.     int n = sizeof(A)/sizeof(int);
  86.  
  87.     print(A,n);
  88.  
  89.     mergeSort(A,0,n - 1);
  90.  
  91.     print(A,n);
  92.  
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0s 9424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[ 1  7  3  8  5  2  9 ]

[ 1  2  3  5  7  8  9 ]
https://ideone.com/Oi7zYq
language:
C (gcc 8.3)
created:
4 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!