Non ti ho detto di ordinare l'array, ma ordinarlo parzialmente. Per il k-esimo elemento ti bastano al più k iterazioni del ciclo interno di un bubblesort (meno se non avvengono scambi <=> array già ordinato). Oppure k estrazioni da un heap. Puoi costruire un heap da un array in spazio costante.
