A Super-Logarithmic Lower Bound for Shuffle-Unshuffle Sorting Networks

Free registration required

Executive Summary

A variety of different classes of sorting networks have been described in the literature. Of particular interest here are the so-called AKS network discovered by Ajtai, Komlos, and Szemeredi, and the sorting networks proposed by Batcher. While the AKS network is the only known sorting network with O (lgn) depth, it also suffers from two significant shortcomings. First, the multiplicative constant hidden by the O-notation is impractically large. Through a series of improvements, this constant has been reduced to below 20, but remains impractical.

  • Format: PDF
  • Size: 191.2 KB