QuickSort_v9

#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) {
  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 < 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 = QuickSelect(new_med);
  if (sh) {
    cout << "QuickSelect res = " << res << "\n\n";
  }
  return res;
}

vector<int> DQS(vector<int> aa) {
    constexpr int kInfin = 2e9;
    if (aa.size() == 1) {
      return aa;
    }
    if (aa.size() == 2) {
      return {min(aa[0], aa[1]), max(aa[0], aa[1])};
    }
    if (sh) {
      cout << "DQS\n";
      cout << "aa\n";
      for (int ii: aa) {
        cout << ii << ' ';
      }
      cout << "\n";
    }
    int piv = QuickSelect(aa);
    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
*/