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