fork download
copy 
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void merge(int *arr, int s, int e) {
  5.  
  6.     int mid = (s+e)/2;
  7.  
  8.     int len1 = mid - s + 1;
  9.     int len2 = e - mid;
  10.  
  11.     int *first = new int[len1];
  12.     int *second = new int[len2];
  13.  
  14.     //copy values
  15.     int mainArrayIndex = s;
  16.     for(int i=0; i<len1; i++) {
  17.         first[i] = arr[mainArrayIndex++];
  18.     }
  19.  
  20.     mainArrayIndex = mid+1;
  21.     for(int i=0; i<len2; i++) {
  22.         second[i] = arr[mainArrayIndex++];
  23.     }
  24.  
  25.     //merge 2 sorted arrays     
  26.     int index1 = 0;
  27.     int index2 = 0;
  28.     mainArrayIndex = s;
  29.  
  30.     while(index1 < len1 && index2 < len2) {
  31.         if(first[index1] < second[index2]) {
  32.             arr[mainArrayIndex++] = first[index1++];
  33.         }
  34.         else{
  35.             arr[mainArrayIndex++] = second[index2++];
  36.         }
  37.     }   
  38.  
  39.     while(index1 < len1) {
  40.         arr[mainArrayIndex++] = first[index1++];
  41.     }
  42.  
  43.     while(index2 < len2 ) {
  44.         arr[mainArrayIndex++] = second[index2++];
  45.     }
  46.  
  47.     delete []first;
  48.     delete []second;
  49.  
  50. }
  51.  
  52. void mergeSort(int *arr, int s, int e) {
  53.  
  54.     //base case
  55.     if(s >= e) {
  56.         return;
  57.     }
  58.  
  59.     int mid = (s+e)/2;
  60.  
  61.     //left part sort karna h 
  62.     mergeSort(arr, s, mid);
  63.  
  64.     //right part sort karna h 
  65.     mergeSort(arr, mid+1, e);
  66.  
  67.     //merge
  68.     merge(arr, s, e);
  69.  
  70. }
  71.  
  72. int main() {
  73.  
  74.     int arr[15] = {3,7,0,1,5,8,3,2,34,66,87,23,12,12,12};
  75.     int n = 15;
  76.  
  77.     mergeSort(arr, 0, n-1);
  78.  
  79.     for(int i=0;i<n;i++){
  80.         cout << arr[i] << " ";
  81.     } cout << endl;
  82.  
  83.     return 0;
  84. }
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1 2 3 3 5 7 8 12 12 12 23 34 66 87
https://ideone.com/zxBnbX
language:
C++ (gcc 8.3)
created:
3 days 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!