An oblivious Top- \(k\) algorithm selects the k smallest elements from d elements while ensuring the sequence of operations and memory accesses do not depend on the input. In 1969, Alekseev proposed an oblivious Top- \(k\) algorithm with complexity \(O(d\log ^2{k})\) , which was later improved by Yao in 1980 for small \(k\ll \sqrt{d}\) . In this paper, we revisit the literature on oblivious Top- \(k\) and propose another improvement of Alekseev’s method that outperforms both for large \(k = \varOmega (\sqrt{d})\) . Our construction is equivalent to applying a new truncation technique to Batcher’s odd-even sorting algorithm. In addition, we propose a combined network to take advantage of both Yao’s and our technique that achieves the best concrete performance, in terms of the number of comparators, for any k. To demonstrate the efficiency of our combined Top- \(k\) network, we implement a secure non-interactive k-nearest neighbors classifier using homomorphic encryption as an application. Compared with the work of Zuber and Sirdey (PoPETS 2021) where oblivious Top- \(k\) was realized with complexity \(O(d^2)\) , our experimental results show a speedup of up to 47 times (not accounting for difference in CPU) for \(d = 1000\) .