fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. void Merge(vector <int>& nums, int left, int mid, int right)
  6. {
  7.     vector <int> leftPart, rightPart;
  8.     for(int i=left;i<=right;i++)
  9.     {
  10.         if(i<=mid)
  11.         {
  12.             leftPart.push_back(nums[i]);
  13.         }
  14.         else
  15.         {
  16.             rightPart.push_back(nums[i]);
  17.         }
  18.     }
  19.     int leftIdx = 0, rightIdx = 0, numsIdx = left;
  20.     while(1)
  21.     {
  22.         if(leftPart[leftIdx] < rightPart[rightIdx])
  23.         {
  24.             nums[numsIdx] = leftPart[leftIdx];
  25.             numsIdx++;
  26.             leftIdx++;
  27.         }
  28.         else
  29.         {
  30.             nums[numsIdx] = rightPart[rightIdx];
  31.             numsIdx++;
  32.             rightIdx++;
  33.         }
  34.         if(leftIdx >= leftPart.size() || rightIdx >= rightPart.size())
  35.             break;
  36.     }
  37.     while(leftIdx < leftPart.size())
  38.     {
  39.         nums[numsIdx] = leftPart[leftIdx];
  40.         numsIdx++;
  41.         leftIdx++;
  42.     }
  43.     while(rightIdx < rightPart.size())
  44.     {
  45.         nums[numsIdx] = rightPart[rightIdx];
  46.         numsIdx++;
  47.         rightIdx++;
  48.     }
  49. }
  50.  
  51. void MergeSort(vector <int>& nums, int left, int right)
  52. {
  53.     if(left == right)
  54.     {
  55.         return;
  56.     }
  57.     int mid = (left+right)/2;
  58.     MergeSort(nums,left,mid);
  59.     MergeSort(nums,mid+1,right);
  60.     Merge(nums,left,mid,right);
  61. }
  62.  
  63. int main()
  64. {
  65.     int n;
  66.     cin>>n;
  67.     vector <int> nums;
  68.     for(int i=0;i<n;i++)
  69.     {
  70.         int x;
  71.         cin>>x;
  72.         nums.push_back(x);
  73.     }
  74.     MergeSort(nums,0,n-1);
  75.     for(int i=0;i<n;i++)
  76.     {
  77.         cout<<nums[i]<<" ";
  78.     }
  79. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
10
15 3 10 -1 7 13 5 -3 1 28
stdout
copy 
-3 -1 1 3 5 7 10 13 15 28
https://ideone.com/25aJuK
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!