fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <numeric>
  4.  
  5. void merge( int L[], int R[], int l_size, int r_size, int A[] )
  6.     // PRE: l_size > 0; r_size > 0; L[0..l_size-1] is in ascending order;
  7.     //      R[0..r_size-1] is in ascending order; A is allocated to l_size + r_size
  8.     // POST: A[0..l_size+r_size-1] contains all elements of L[0..l_size-1] and R[0..r_size-1]
  9. {
  10.     int i;                                 // counter used to fill A at end of algorithm
  11.     int l_ctr;                             // counter used to traverse L
  12.     int r_ctr;                             // counter used to traverse R
  13.     int a_ctr;                             // counter used to traverse A
  14.  
  15.     l_ctr = 0;
  16.     r_ctr = 0;                             // set all counters equal to zero
  17.     a_ctr = 0;
  18.  
  19.     while ( l_ctr < l_size && r_ctr < r_size ) // loop runs until reaching end of a list
  20.     {
  21.         if ( L[l_ctr] < R[r_ctr] )            // if lowest remain ing value in L is
  22.         {                                     // lower than lowest remaining value in R;
  23.             A[a_ctr] = L[l_ctr];              // set next index of A to L[l_ctr]
  24.             l_ctr++;                          // increment l_ctr by one
  25.         }
  26.         else                                       // else do the same for r_ctr
  27.         {
  28.             A[a_ctr] = R[r_ctr];
  29.             r_ctr++;
  30.         }
  31.         a_ctr++;                                   // increment a_ctr by one
  32.     }
  33.  
  34.     if ( l_ctr < l_size )                          // if all of L has not been seen yet
  35.     {
  36.         for ( i = l_ctr; i < l_size; i++ )         // loop sets remaining values in L
  37.         {                                          // to the last values of A
  38.             A[a_ctr] = L[i];
  39.             a_ctr++;
  40.         }
  41.     }
  42.     else                                           // else do the same for R
  43.     {
  44.         for ( i = r_ctr; i < r_size; i++ )
  45.         {
  46.             A[a_ctr] = R[i];
  47.             a_ctr++;
  48.         }
  49.     }
  50. }
  51.  
  52. void mergeSort( int A[], int p, int q )
  53.     // PRE: p >= 0; q >= 0; A[p..q] is initialized
  54.     // POST: A[p..q] is sorted in ascending order
  55. {
  56.     int i;                                     //  counter used to initialize L and R
  57.     int j;
  58.     int m;                                     // midpoint of A
  59.     int L[100];                                // lower half of A
  60.     int R[100];                                // upper half of A
  61.  
  62.     if ( p < q )                               // if list contains more than one value
  63.     {
  64.         m = ( p + q ) / 2;                     // find midpoint
  65.  
  66.         mergeSort( A, p, m );                  // call mergeSort for lower half of array
  67.         mergeSort( A, m + 1, q );              // call mergeSort for upper half of array
  68.  
  69.         j = 0;
  70.  
  71.         for ( i = p; i <= m; i++ )             // initialize lower half of array
  72.         {
  73.             L[j] = A[i];
  74.             j++;
  75.         }
  76.  
  77.         j = 0;
  78.  
  79.         for ( i = m + 1; i <= q; i++ )         // initialize upper half of array
  80.         {
  81.             R[j] = A[i];
  82.             j++;
  83.         }
  84.  
  85.         merge( L, R, m - p + 1, q - m, A+p );    // merge both sides
  86.     }
  87. }
  88.  
  89.  
  90. int main(int, char *[])
  91. {
  92.     int data[100];
  93.     std::iota(data, data + 100, 0); // fill 0,1,2...
  94.     std::random_shuffle(data, data + 100); // shuffle
  95.  
  96.     for (int n : data) {
  97.         std::cout << n << ' ';
  98.     }
  99.     std::cout << "\n\n";
  100.  
  101.     mergeSort(data, 0, 99);
  102.  
  103.     for (int n : data) {
  104.         std::cout << n << ' ';
  105.     }
  106.     std::cout << '\n';
  107. }
  108.  
Success #stdin #stdout 0s 3296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
92 51 11 69 24 35 17 36 26 98 67 39 83 2 75 56 59 18 32 40 91 86 57 12 14 42 27 62 63 58 30 96 13 68 3 87 71 64 9 22 66 80 20 79 89 81 73 0 94 41 88 28 52 43 16 60 49 7 84 72 29 61 6 45 53 76 8 33 37 15 25 55 70 31 82 47 48 10 90 34 23 74 77 19 85 44 93 54 97 1 38 95 4 21 99 5 78 65 50 46 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
https://ideone.com/yT292J
language:
C++14 (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!