QuickSort_v11_TL

#include <cmath>
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::max;
using std::min;
using std::string;
using std::vector;

bool sh = false;

void Swap(int* p1, int* p2) {
  int tt = *p1;
  *p1 = *p2;
  *p2 = tt;
}

vector<int> Partition(vector<int> aa, int xx) {
  // делим на < и >=
  int nn = aa.size();
  int ll = -1;
  for (int ii = 0; ii < nn; ++ii) {
    if (aa[ii] < xx) {
      int* p1 = &aa[ii];
      int* p2 = &aa[ll + 1];
      Swap(p1, p2);
      ll++;
    }
  }
  // делим на = и >
  for (int ii = ll + 1; ii < nn; ++ii) {
    if (aa[ii] == xx) {
      int* p1 = &aa[ii];
      int* p2 = &aa[ll + 1];
      Swap(p1, p2);
      ll++;
    }
  }
  return aa;
}

int GetMed(vector<int> vv) {
  for (int ii = 0; ii < 5; ++ii) {
    for (int jj = 0; jj < 4; ++jj) {
      if (vv[jj] > vv[jj + 1]) {
        int* p1 = &vv[jj];
        int* p2 = &vv[jj + 1];
        Swap(p1, p2);
      }
    }
  }
  /*if (sh) {
    cout << "vv sorted\n";
    for (int ii: vv) {
      cout << ii << ' ';
    }
    cout << "\n\n";
  }*/
  return vv[2];
}

vector<int> DQS(vector<int> aa);

int QuickSelect(vector<int> med, int cnt) {
  constexpr int kInfin = 2e9;
  while (med.size() % 5 != 0) {
    med.push_back(kInfin);
  }
  if (sh) {
    cout << "QuickSelect\n";
    cout << "med\n";
    for (int ii : med) {
      cout << ii << ' ';
    }
    cout << "\n";
  }

  vector<int> new_med;
  for (int ii = 0; ii < (int)med.size(); ii += 5) {
    vector<int> vv = {med[ii], med[ii + 1], med[ii + 2], med[ii + 3],
                      med[ii + 4]};
    int kk = GetMed(vv);
    new_med.push_back(kk);
  }
  if (new_med.size() == 1) {
    return new_med[0];
  }
  if (new_med.size() == 2) {
    if (new_med[0] != kInfin) {
      return new_med[0];
    }
    return new_med[1];
  }
  if (new_med.size() <= 5) {
    for (int ii : new_med) {
      if (ii != kInfin) {
        return ii;
      }
    }
    return new_med[2];
  }
  if (sh) {
    cout << "new_med\n";
    for (int ii : new_med) {
      cout << ii << ' ';
    }
    cout << "\n\n";
  }
  new_med = DQS(new_med);
  int res;
  if (cnt == 2) {
    int tt = new_med.size();
    res = new_med[tt / 2];
    return res;
  }
  res = QuickSelect(new_med, cnt + 1);
  if (sh) {
    cout << "QuickSelect res = " << res << "\n\n";
  }
  return res;
}

vector<int> DQS(vector<int> aa) {
  if (aa.size() == 1) {
    return aa;
  }
  if (aa.size() == 2) {
    return {min(aa[0], aa[1]), max(aa[0], aa[1])};
  }
  int piv = QuickSelect(aa, 1);
  aa = Partition(aa, piv);
  if (sh) {
    cout << "PERTITION DONE\n";
    cout << "piv = " << piv << "\n";
    cout << "aa\n";
    for (int ii : aa) {
      cout << ii << ' ';
    }
    cout << "\n\n";
  }
  vector<int> bb;  //<piv
  vector<int> cc;  //==piv
  vector<int> dd;  //>piv
  for (int ii : aa) {
    if (ii < piv) {
      bb.push_back(ii);
    } else if (ii == piv) {
      cc.push_back(ii);
    } else {
      dd.push_back(ii);
    }
  }
  if (!bb.empty()) {
    bb = DQS(bb);
  }
  if (!dd.empty()) {
    dd = DQS(dd);
  }
  vector<int> res;
  for (int ii : bb) {
    res.push_back(ii);
  }
  for (int ii : cc) {
    res.push_back(ii);
  }
  for (int ii : dd) {
    res.push_back(ii);
  }
  return res;
  if (sh) {
    cout << "res\n";
    for (int ii : res) {
      cout << ii << ' ';
    }
    cout << "\n";
  }
}

int main() {
  /*std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);*/
  int nn;
  cin >> nn;
  vector<int> aa(nn);
  for (int& ii : aa) {
    cin >> ii;
  }
  if (sh) {
    cout << "BEGIN SORT\n";
  }
  aa = DQS(aa);
  if (sh) {
    cout << "SORTED aa\n";
  }
  for (int ii : aa) {
    cout << ii << ' ';
  }
  cout << "\n";
}
/*
17
2 2 0 2 1 2 0 2 1 0 2 1 2 2 0 0 2

16
7 10 3 4 5 11 2 1 2 3 1 5 4 6 7 1
*/