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