QuickSort_AGAIN_OK

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

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

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

vector<int> ar;

void Partition(int low, int high, int xnum) {
  // делим на < и >=
  int lft = low - 1;
  for (int id = low; id <= high; ++id) {
    if (ar[id] < xnum) {
      int* p1 = &ar[id];
      int* p2 = &ar[lft + 1];
      Swap(p1, p2);
      lft++;
    }
  }
  // делим на = и >
  for (int id = lft + 1; id <= high; ++id) {
    if (ar[id] == xnum) {
      int* p1 = &ar[id];
      int* p2 = &ar[lft + 1];
      Swap(p1, p2);
      lft++;
    }
  }
}

void QuickSort(int low, int high) {
  if (low >= high) {
    return;
  }
  int piv = ar[low];
  Partition(low, high, piv);
  int lft = low;
  while (ar[lft] != piv) {
    lft++;
  }
  int rgt = high;
  while (ar[rgt] != piv) {
    rgt--;
  }
  // lft - самый левый piv
  // rgt - самый правый piv
  QuickSort(low, lft - 1);
  QuickSort(rgt + 1, high);
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  int len;
  cin >> len;
  ar.resize(len);
  for (int& el : ar) {
    cin >> el;
  }
  // Partition(0, len - 1, 5);
  QuickSort(0, len - 1);
  for (int el : ar) {
    cout << el << ' ';
  }
}
/*
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
*/