Нужно исключить проблему, когда на вход подаются большие последовательности одинаковых чисел и quick sort работает за O(n^2)

void swap(int input_arr[], int index_1, int index_2){
    int temp;
    temp = input_arr[index_1];
    input_arr[index_1] = input_arr[index_2];
    input_arr[index_2] = temp;
}

int partition(int input_arr[], int left, int right) {
    int pivot;
    int random_index = left + (rand()%(right - left));
    pivot = input_arr[random_index];
    swap(input_arr, random_index, right);
    
    int wall = left;
    int temp;

    for (int i = left; i < right; i++) {
        if (input_arr[i] <= pivot) {
            temp = input_arr[wall];
            input_arr[wall] = input_arr[i];
            input_arr[i] = temp;
            wall++;
        }
    }

    temp = input_arr[wall];
    input_arr[wall] = input_arr[right];
    input_arr[right] = temp;

    return wall;
}

void quickSort(int input_arr[], int left, int right, int k) {


    if (left < right) {
        int partition_index = partition(input_arr, left, right);

        if (partition_index < k) {
            quickSort(input_arr, partition_index + 1, right, k);
        }
        if (partition_index == k) {

        }
        if (partition_index > k) {
            quickSort(input_arr, left, partition_index - 1, k);
        }
    }
}