Safely sorting secret data Suppose you have a secret list of n distinct integers. How would you sort this list in a way that is not vulnerable to timing attacks? I tried looking up &quot;constant time sorting&quot; and other related queries but that expectedly lead nowhere.
Yes, you can; you can use Batcher's Merge Exchange algorithm, paired with a constant time/access compare-and-swap routine (which reads two elements from locations A and B, and writes the larger element into location A and the smaller element into location B).
This takes $O(n (\log n)^2)$ time, which makes it not quite as fast as other sort algorithms; however if you want constant time/memory accesses, that's about the best we have.
The code on Wikipedia assumes that $n$ is a power of two; it is not hard to extend it to arbitrary $n$...