fork download
  1. #include <algorithm>
  2. #include <string>
  3. #include <vector>
  4.  
  5. template<typename I>
  6. void MergeSort(I first, I last) {
  7. if (last - first > 1) {
  8. I mid = first + (last - first) / 2;
  9. MergeSort(first, mid);
  10. MergeSort(mid, last);
  11. std::inplace_merge(first, mid, last);
  12. }
  13. }
  14.  
  15. int main() {
  16. for (int method = 3; method < 4; ++method) {
  17. std::vector<std::string> a(1000000);
  18. unsigned first = 0;
  19. unsigned last = a.size();
  20. for (unsigned i = 0; i < 100; ++i) {
  21. const std::string s = std::string()
  22. + (char)('a' + i / 25)
  23. + (char)('a' + i % 25);
  24. for (unsigned j = 0; j < i + 2; ++j) {
  25. a[first++] = s;
  26. }
  27. a[--last] = s;
  28. }
  29. for (unsigned pos = first; pos < last; ++pos) {
  30. a[pos] = std::string() + "z"
  31. + (char)('a' + pos % 23);
  32. }
  33. switch (method) {
  34. case 0:
  35. std::sort(a.begin(), a.end());
  36. break;
  37. case 1:
  38. std::partial_sort(a.begin(), a.end(), a.end());
  39. break;
  40. case 2:
  41. std::stable_sort(a.begin(), a.end());
  42. break;
  43. case 3:
  44. MergeSort(a.begin(), a.end());
  45. break;
  46. }
  47. }
  48. return 0;
  49. }
  50.  
Success #stdin #stdout 1.46s 27240KB
stdin
Standard input is empty
stdout

Standard output is empty