A simple architecture for constant time sorting machines.
Journal
SIGARCH Computer Architecture News
Journal Volume
23
Journal Issue
1
Pages
13-19
Date Issued
1995
Author(s)
Hsu, Tsong-Chih
Abstract
In this paper, we propose a constant time sorting algorithm on an array composed of comparators and single-pole-double-throw switches, which is far more feasible than other constant time sorting algorithms [21]-[23]. Our results shown that the algorithm uses time T = Θ(1) and area A = O ( N 3 ). This nearly matches the AT 2 = Ω( N 2 log 2 N ) lower bound for sorting in the VLSI model.
Type
journal article