fork(3) download 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void merge(int* A, int p, int q, int r) {       // MERGE(A,p,q,r)
  5.     int n1 = q-p+1;                             //   1. n1 = q-p+1
  6.     int n2 = r-q;                               //   2. n2 = r-q 
  7.  
  8.     int i,j,k;
  9.     int *L=new int[n1+1], *R = new int[n2+1];   //   3. let L[1...n1+1] and R[1..n2+1] be new arrays
  10.  
  11.     for(i=0; i<n1; i++)                         //   4. for i = 1 to n1
  12.         L[i]=A[p+i];                            //   5.    L[i] = A[p+i-1]
  13.  
  14.     for(j=0; j<n2;j++)                          //   6. for j = 1 to n2
  15.         R[j]=A[q+j+1];                            //   7.    R[j] = A[q+j]
  16.  
  17.     L[n1]=999; //sentinel                       //   8. L[n1+1]= ∞
  18.     R[n2]=999; //sentinel                       //   9. R[n2+1]= ∞
  19.     i=0;                                        //  10. i = 1
  20.     j=0;                                        //  11. j = 1
  21.     for(k=p; k<=r; k++) {                        //  12. for k = p to r 
  22.         if(L[i]<=R[j])                          //  13.    if(L[i]<=R[j])
  23.             A[k]=L[i++];                        //  14.         A[k] = L[i]
  24.                                                 //  15.         i = i+1
  25.         else                                    //  16.    else A[k] = R[j]
  26.             A[k]=R[j++];                        //  17.         j = j+1                 
  27.     }
  28. }
  29.  
  30. void mergeSort(int* a, int p, int r) {        // MERGE-SORT (A,p,r)
  31.     if(p<r) {                                 //  1. if p<r 
  32.         int q=(p+r)/2;                        //  2.   q = (p+r)/2 
  33.         mergeSort(a,p,q);                     //  3.   MERGE-SORT(A,p,q)
  34.         mergeSort(a,q+1,r);                   //  4.   MERGE-SORT(A,q+1,r)
  35.         merge(a,p,q,r);                       //  5.   MERGE(A,p,q,r)
  36.     }
  37. }
  38.  
  39. int main() {
  40.     int arr[]={5,4,3,2,1};
  41.     mergeSort(arr,0,4);
  42.  
  43.     for(int i=0; i<5; i++)
  44.         cout << arr[i]<<" ";
  45. }
Success #stdin #stdout 0s 3228KB
comments ()
stdin 
Standard input is empty
stdout 
1 2 3 4 5
https://ideone.com/BoJUSi
language:
C++ (gcc 8.3)
created:
9 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!