International Association
for Cryptologic Research

Outsourcing computations to cloud providers raises significant data privacy concerns, making Privacy-Preserving Computation via Fully Homomorphic Encryption (FHE) increasingly vital. However, adapting data sorting routines to the FHE domain introduces severe performance bottlenecks. This survey systematizes the state-of-the-art in FHE-based sorting algorithms. A novel complexity metric, FHE-Effort, is introduced to accurately evaluate homomorphic circuit efficiency. Eighteen algorithms are benchmarked across three major FHE schemes using a unified codebase. The analysis concludes that TFHE is currently the most efficient scheme for sorting applications, and sorting networks like Odd-Even Merge and Bitonic Sort offer the optimal algorithmic architectures.