Note: |
|
(LaTeX) Abstract: |
In all recent near-optimal sorting algorithms for meshes, the
packets are sorted with respect to some snake-like indexing. In
this paper we present deterministic algorithms for sorting with
respect to the more natural row-major indexing.
For 1-1 sorting on an $n \times n$ mesh, we give an algorithm that
runs in $2 \cdot n + o(n)$ steps, matching the distance bound, with
maximal queue size five. It is considerably simpler than earlier
algorithms. Another algorithm performs $k$-$k$ sorting in $k \cdot
n / 2 + o(k \cdot n)$ steps, matching the bisection bound.
Furthermore, we present {\em uni-axial} algorithms for row-major
sorting. We show that 1-1 sorting can
be performed in $2\breukk{1}{2} \cdot n + o(n)$ steps.
Alternatively, this problem is solved with maximal queue size five
in $4\breukk{1}{3} \cdot n$ steps, without any additional terms. |
URL for the Abstract: |
|
Categories,
Keywords: |
Algorithms, Meshes, Routing, Sorting, Row-Major |
HyperLinks / References / URLs: |
|
Copyright Message: |
|
Personal Comments: |
|
Download
Access Level: |
Public |
|