Tagged Up/Down Sorter--A Hardware Priority Queue
Simon W. Moore · The Computer Journal · 1995
We present a hardware oriented priority queue algorithm requiring [equation: see PDF] comparators and swappers to maintain an n item queue. It supports two operations, insert and extract minimum (or alternatively, extract maximum), both of which operate in a single cycle. Thus, sorting time is O(n). Records with identical keys are always extracted in FIFO order of insertion. A formal proof of correctness of these sorting and FIFO characteristics is presented.