A Comparison-Based Algorithm for Hardware- and SoftwareBased Median-Finding in Signal Processing Applications

Authors
Behrooz Parhami
Saleh Abdel-hafeez
Arwa Damir
Abstract
Finding the median value in a list of numbers is an important computational task that is useful for a variety of problems in domains such as computing, networking, signal processing, and remote sensing. Algorithms with worst-case running times that vary linearly with the problem size are known. As is the case for sorting, however, algorithms with non-optimal worst-case running times but with better average performance for problem sizes of practical interest do exist. We devise one such algorithm based on comparisons, analyze its running time, and experimentally verify its performance for applications with small-to-moderate input lists.

Keywords