Chipress

In a previous post, we discussed one possible array sort solution without comparators. There are more comparison-free array sorting implementations available.

In paper “An Efficient O(N) Comparison-Free Sorting Algorithm”, Saleh Abel-Hafeez and Ann Gordon-Ross proposed a new sorting algorithm, targeted for custom, IC-designed applications, such as GPU, and video processing DSP chips.

The idea is to convert the array sorting into linear algebra vector computations. See the diagram below for example.

Their sorting design does not require any comparison-swapping, complex circuitry, or SRAMs. It processes data in a forward moving direction, and achieves sorting latency always linearly proportional to the number of array elements N, or O(N) time complexity.

We only covered some basic ideas of their solution, and we encourage interviewees to read their original paper for more details.

Reference

1. “An Efficient O(N) Comparison-Free Sorting Algorithm” by Saleh Abel-Hafeez and Ann Gordon-Ross