fork download
copy 
  1. // Merge Sort example
  2. // For input array
  3. // 2 8 7 1 3 5 6 4 9 0
  4. //
  5. // First partion in L[] and R[] will be
  6. // L[] = 2 8 7 1 3 ==> L[] = 2 8 7 | R[] = 1 3 ==> L[] = 2 8 | R[] = 7
  7. // R[] = 5 6 4 9 0
  8. //
  9. #include <stdio.h>
  10.  
  11. #define EOA 100000  //End of array
  12.  
  13. // To enable debug messages uncomment #define
  14. // #define DEBUG 1
  15.  
  16. #ifdef DEBUG
  17. #  define D(x) x
  18. #else
  19. #  define D(x)
  20. #endif
  21.  
  22. void mergesort(int arr[], int p, int r); 
  23. void merge(int arr[], int p, int q, int r); 
  24.  
  25. int arr[10] = {2, 8, 7, 1, 3, 5, 6, 4, 9, 0}; 
  26.  
  27. int main()
  28. {
  29.     int i = 0;
  30.     printf("Input array\n");
  31.     for (i = 0; i <= 9; i++) {
  32.         printf("%d ", arr[i]);
  33.     }   
  34.     printf("\n\n");
  35.  
  36.     mergesort(arr, 0, 9); 
  37.  
  38.     printf("Sorted output\n");
  39.     for (i = 0; i <= 9; i++) {
  40.         printf("%d ", arr[i]);
  41.     }   
  42.     printf("\n");
  43.  
  44.     return 0;
  45. }
  46.  
  47. void mergesort(int arr[], int p, int r)
  48. {
  49.     if (p < r) {
  50.         int q = (p + r) / 2;
  51.  
  52.         mergesort(arr, p, q);
  53.         mergesort(arr, q+1, r);
  54.         merge(arr, p, q, r);
  55.     }
  56. }
  57.  
  58. void merge(int arr[], int p, int q, int r)
  59. {
  60.     int n1 = q - p + 1;
  61.     int n2 = r - q;
  62.     int i = 0;
  63.     int j = 0;
  64.  
  65.     int L[15];
  66.     int R[15];
  67.  
  68.     //Copy elements from p to n1 in L[]
  69.     for (i = 0; i < n1; i++) {
  70.         L[i] = arr[p + i];
  71.     }
  72.     L[i] = EOA;
  73.  
  74.     for (j = 0; j < n2; j++) {
  75.         R[j] = arr[q + j + 1];
  76.     }
  77.     R[j] = EOA;
  78.  
  79.     int lindx = 0;
  80.     int rindx = 0;
  81.     //Merge array L[] and R[]
  82.     for (i = p; i <= r; i++) {
  83.         if(L[lindx] <= R[rindx]) {
  84.             arr[i] = L[lindx++];
  85.         } else {
  86.             arr[i] = R[rindx++];
  87.         }
  88.     }
  89.  
  90.     // Print debug statements
  91.     D(printf("\n######################\n"));
  92.     D(printf("Left array\n"));
  93.  
  94.     for (i = 0; i < n1; i++) {
  95.         D(printf("%d ", L[i]));
  96.     }
  97.  
  98.     D(printf("\nRight array\n"));
  99.     for (i = 0; i < n2; i++) {
  100.         D(printf("%d ", R[i]));
  101.     }
  102.  
  103.     D(printf("\nAfter Merge\n"));
  104.     for (i = p; i <= r; i++) {
  105.         D(printf("%d ", arr[i]));
  106.     }
  107.     D(printf("\n\n"));
  108. }
  109.  
Success #stdin #stdout 0s 2248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Input array
2 8 7 1 3 5 6 4 9 0 

Sorted output
0 1 2 3 4 5 6 7 8 9
https://ideone.com/BuLW5z
Merge Sort
language:
C (gcc 8.3)
created:
10 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!