fork download 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void merge(int arr[], int l, int m, int r)
  5. {
  6.     int i, j, k;
  7.     int n1 = m - l + 1;
  8.     int n2 = r - m;
  9.  
  10.     int L[n1], R[n2];
  11.  
  12.     for (i = 0; i < n1; i++)
  13.         L[i] = arr[l + i];
  14.     for (j = 0; j < n2; j++)
  15.         R[j] = arr[m + 1 + j];
  16.  
  17.     i = 0;
  18.     j = 0;
  19.     k = l;
  20.     while (i < n1 && j < n2) {
  21.         if (L[i] <= R[j]) {
  22.             arr[k] = L[i];
  23.             i++;
  24.         }
  25.         else {
  26.             arr[k] = R[j];
  27.             j++;
  28.         }
  29.         k++;
  30.     }
  31.     while (i < n1) {
  32.         arr[k] = L[i];
  33.         i++;
  34.         k++;
  35.     }
  36.  
  37.     while (j < n2) {
  38.         arr[k] = R[j];
  39.         j++;
  40.         k++;
  41.     }
  42. }
  43.  
  44. void mergeSort(int arr[], int n){
  45. 	int left_start, right_end, mid, curr_size=1;
  46. 	for(curr_size=1;curr_size<=n-1; curr_size*=2){
  47. 		for(left_start = 0; left_start<n-1;left_start+=curr_size){
  48. 			mid = min(left_start+curr_size-1,n-1);
  49. 			right_end = min(left_start+curr_size*2-1,n-1);
  50. 			merge(arr,left_start, mid, right_end);
  51.  
  52. 		}
  53. 	}
  54. }
  55.  
  56. void printArray(int A[], int size)
  57. {
  58.     int i;
  59.     for (i = 0; i < size; i++)
  60.         cout << A[i] << " ";
  61.     cout << endl;
  62. }
  63.  
  64. int main()
  65. {
  66.     int arr[] = { 12, 11, 13, 5, 6,8,9 };
  67.     int arr_size = 7;
  68.  
  69.     cout << "Given array is \n";
  70.     printArray(arr, arr_size);
  71.  
  72.     mergeSort(arr, arr_size);
  73.  
  74.     cout << "\nSorted array is \n";
  75.     printArray(arr, arr_size);
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0.01s 5432KB
comments (?)
stdin 
Standard input is empty
stdout 
Given array is 
12 11 13 5 6 8 9 

Sorted array is 
5 6 8 9 11 12 13
https://ideone.com/yAu4Wb
language:
C++14 (gcc 8.3)
created:
2 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!