#
Zig-zag Sort: A simple deterministic data-oblivious sorting algorithm
running in $O(n\log n)$ time

##
Michael T. Goodrich

We describe and analyze Zig-zag Sort--a deterministic data-oblivious
sorting algorithm running in $O(n\log n)$ time that is arguably simpler
than previously known algorithms with similar properties, which are
based on the AKS sorting network. Because it is data-oblivious and
deterministic, Zig-zag Sort can be implemented as a simple $O(n\log
n)$-size sorting network, thereby providing a solution to an open
problem posed by Incerpi and Sedgewick in 1985. In addition, Zig-zag
Sort is a variant of Shellsort, and is, in fact, the first deterministic
Shellsort variant running in $O(n\log n)$ time. The existence of such an
algorithm was posed as an open problem by Plaxton et al. in 1992 and
also by Sedgewick in 1996. More relevant for today, however, is the fact
that the existence of a simple data-oblivious deterministic sorting
algorithm running in $O(n\log n)$ time simplifies the inner-loop
computation in several proposed oblivious-RAM simulation methods (which
utilize AKS sorting networks), and this, in turn, implies simplified
mechanisms for privacy-preserving data outsourcing in several cloud
computing applications. We provide both constructive and
non-constructive implementations of Zig-zag Sort, based on the existence
of a circuit known as an epsilon-halver, such that the constant factors
in our constructive implementations are orders of magnitude smaller than
those for constructive variants of the AKS sorting network, which are
also based on the use of epsilon-halvers.

(Practice talk for a paper to be presented at STOC 2014.)