Оптимизация QuickSort на C++

Всем доброго времени суток! Я хочу написать оптимизированный алгоритм быстрой сортировки для задачи, в которой нужно вывести k-й элемент, если массив будет отсортирован в порядке возрастания. Массив задаётся довольно необычным способом: даны числа A, B, C и даны первые 2 элемента, а остальные предлагается вычислить следующим образом: a[i] = A * a[i - 2] + B * a[i - 1] + C (для i >= 2). Причём массив надо задавать int-овый, значения в элементах могут переполняться - так и надо по условию. Очевидно, что получается неотсортированный массив, поэтому я сортирую массив, при этом рассматриваю только ту часть, где лежит k. В конце концов просто вывожу элемент по этому индексу. Но не проходит по времени... Подскажите, пожалуйста, что я делаю не так?

P.S. в первой строке даны n - размер массива, k - индекс необходимого элемента при нумерации с 1; во второй - A, B, C, a[0], a[1].

P.P.S. Если кто-то может предложить алгоритм с rand(), который точно будет работать быстрее, то, пожалуйста, поделитесь своими идеями!

#include <fstream>

using namespace std;

void QSort(int arr[], int left, int right, int k) {
    int key = arr[(left + right) / 2];
    int i, j;

    do {
        for (i = left; arr[i] < key; i++);

        for (j = right; key < arr[j]; j--);

        if (i <= j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;

            i++;
            j--;
        }
    } while (i <= j);

    if (left <= k && k <= j && left < j)
        QSort(arr, left, j, k);

    if (i <= k && k <= right && i < right)
        QSort(arr, i, right, k);
}

int main() {
    int n, k;
    int A, B, C;

    ifstream in;
    in.open("kth.in");

    in >> n >> k;
    int arr[n];
    in >> A >> B >> C >> arr[0] >> arr[1];

    in.close();

    for (int i = 2; i < n; i++)
        arr[i] = A * arr[i - 2] + B * arr[i - 1] + C;

    QSort(arr, 0, n - 1, k - 1);

    ofstream out;
    out.open("kth.out");

    out << arr[k - 1];

    out.close();
    return 0;
}