Tamir Levi, Ph.D. Thesis Seminar
Wednesday, 5.5.2010, 14:30
A Bitonic sorter is a comparator network that sorts every Bitonic input sequence. In our research, we
studied the minimal depth of such networks. Building on previous works, we establish that
the minimal depth of a Bitonic sorter of n keys is 2ceiling(log(n)) -floor(log(n)).
This result is constructive - that is, we present, for every n, a Bitonic sorter of that depth.
In this talk I will also present other results from my PhD research.