Как найти k-е наименьшее целое число в несортированном массиве без сортировки массива?

Итак, мне дан (несортированный) массив A из N различных целых чисел, я пытаюсь реализовать алгоритм «разделяй и властвуй», чтобы найти K-й наименьший элемент (K ≤ N) в массив (т.е. он будет наименьшим в целом, если K = 1). Алгоритм возвращает значение K-го наименьшего элемента в массиве. Мне нужно, чтобы он работал за время O (N) в среднем случае. Может ли кто-нибудь дать мне несколько советов?