class Solution {
public:
int InsertSort(vector<int>& a, int l, int r){
for(int i = l + 1; i <= r; i++){
auto x = a[i];
auto j = i;
while(j > l && x < a[j-1]){
a[j] = a[j-1];
j--;
}
a[j] = x;
}
return l + (r - l) / 2;
}
int Partiton(vector<int>& a, int l, int r, int m){
int x = a[m];
int i = l;
int j = r;
swap(a[m], a[l]);
while(i < j){
while(i < j && a[j] >= x) j--;
a[i] = a[j];
while(i < j && a[i] <= x) i++;
a[j] = a[i];
}
a[i] = x;
return i;
}
int FindMid(vector<int>& a, int l, int r){
if(r - l + 1 < 5) return InsertSort(a, l, r);
int p = l - 1;
for(int i = l; i < r - 5; i += 5){
int mid = InsertSort(a, i, i+4);
swap(a[++p], a[mid]);
}
return FindMid(a, l, p);
}
int BFPRT(vector<int>& a, int l, int r, int k){
if(l == r) return a[l];
int m = FindMid(a, l, r);
int p = Partiton(a, l, r, m);
int n = p - l + 1;
if(n == k) return a[p];
if(n > k) return BFPRT(a, l, p, k);
return BFPRT(a, p+1, r, k - n);
}
int findKthLargest(vector<int>& nums, int k) {
return BFPRT(nums, 0, nums.size()-1, nums.size() - k + 1);
}
};