Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm ... - todo314 @ ウィキ

Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(nlogn) Time

• Michael T. Goodrich
• STOC 2014

• data-oblivious
• シェルソート
  • i mod hでグループ分けして挿入ソートしていく
  • hを小さくしていく
• Zig-zagは？: AKSソートより単純
• ε-halver

• n = 2^k
• 以下をk回繰り返す
• splitting step
  • 2個に分割
• outer zig
• outer zag

• 未解決問題
  • サイズO(nlogn)の単純なソーティングネットワークを構成する
• を解決した

STOC ソート

2014-10-03 17:46:28 (Fri)