Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time

We describe 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 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.

Authors

• Michael T. Goodrich

Keywords

No keywords are indexed for this paper.