fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4.  
  5. template<class T>
  6. void merge(std::vector<T>& v, int p, int q, int r)
  7. {
  8. int size1 = q-p+1;
  9. int size2 = r-q;
  10. std::vector<T> L(size1);
  11. std::vector<T> R(size2);
  12.  
  13. for(int i = 0; i < size1; i++)
  14. {
  15.     L[i] = v[p+i];
  16. }
  17. for(int j = 0; j < size2; j++)
  18. {
  19.     R[j]=v[q+j+1];
  20. }
  21.  
  22. int i=0,j=0;
  23. int k;
  24. for(k = p; k <= r && i < size1 && j < size2; k++)
  25. {
  26.     if(L[i] <= R[j])
  27.     {
  28.         v[k] = L[i];
  29.         i++;
  30.     }
  31.     else
  32.     {
  33.         v[k] = R[j];
  34.         j++;
  35.     }
  36. }
  37. for(i = i; i < size1; ++i)
  38. {
  39.     v[k] = L[i];
  40.     k++;
  41. }
  42.  
  43. for(j = j; j < size2; j++)
  44.     {
  45.         v[k] = R[j];
  46.         k++;
  47.     }
  48. }
  49.  
  50. template<class T>
  51. void merge_sort(std::vector<T>& v, int p, int r){
  52. if(p < r)
  53. {
  54.     int q = (p+r)/2;
  55.     merge_sort(v, p, q);
  56.     merge_sort(v, q+1, r);
  57.     merge(v, p, q, r);
  58. }
  59. }
  60.  
  61. int main()
  62. {
  63. std::vector<int>vec;
  64. vec.push_back(13);
  65. vec.push_back(5);
  66. vec.push_back(7);
  67. vec.push_back(7);
  68. vec.push_back(4);
  69. vec.push_back(2);
  70. vec.push_back(10);
  71. int sz = vec.size();
  72. std::cout << "Entered array : ";
  73. for(int n = 0; n < sz; n++){
  74.     std::cout << vec[n] <<" ";
  75. }
  76. std::cout << "\n";
  77. std::cout << "Sorted array : ";
  78. merge_sort(vec, 0, sz-1);
  79. for(int n = 0; n < sz; n++){
  80.     std::cout << vec[n] << " ";
  81. }
  82. std::cout << "\n";
  83.  
  84. std::vector<char> c;
  85. c.push_back('d');
  86. c.push_back('y');
  87. c.push_back('h');
  88. c.push_back('l');
  89. c.push_back('e');
  90. c.push_back('a');
  91. int sz1 = c.size();
  92. std::cout << "Entered array : ";
  93. for(int n = 0; n < sz1; n++){
  94.     std::cout << c[n] <<" ";
  95. }
  96. std::cout << "\n";
  97. std::cout << "Sorted array : ";
  98. merge_sort(c, 0, sz1-1);
  99. for(int n = 0; n < sz1; n++){
  100.     std::cout << c[n] << " ";
  101. }
  102. std::cout << "\n";
  103.  
  104. std::vector<std::string> str;
  105. str.push_back("car");
  106. str.push_back("dog");
  107. str.push_back("apple");
  108. str.push_back("ball");
  109. str.push_back("tree");
  110. int sz2 = str.size();
  111.  
  112. std::cout << "Entered array : ";
  113. for(int n = 0; n < sz2; n++){
  114.     std::cout << str[n] <<" ";
  115. }
  116. std::cout << "\n";
  117. std::cout << "Sorted array : ";
  118. merge_sort(str, 0, sz2-1);
  119. for(int n = 0; n < sz2; n++){
  120.     std::cout << str[n] << " ";
  121. }
  122. std::cout << "\n";
  123.  
  124.     return 0;
  125. }
  126.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Entered array : 13 5 7 7 4 2 10 
Sorted array : 2 4 5 7 7 10 13 
Entered array : d y h l e a 
Sorted array : a d e h l y 
Entered array : car dog apple ball tree 
Sorted array : apple ball car dog tree
https://ideone.com/M7mHMt
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!