# Sorting by boolean algebra (hardware) instead of algorithm (software)

Consider there's an 5 elements list that foreach element are 2-bits. Forexample [01,00,10,00,11], if the list is sorted, we hope the output like this [00,00,01,10,11]

Maybe that case seems complicated, let's move to simple case.

Consider there's an 2 elements list that foreach element are 1-bit. Forexample [1,0], if the list is sorted, we hope the output like this [0,1].

If that simple case is written in general we can make that list like this [A,B] where if the list is sorted the output will be [X,Y] For A,B,X,and Y are 1-bit. (Only 0 and 1)

Hence, we can make this general case to truth table

A B X Y
0 0 0 0 (already sorted)
0 1 0 1 (already sorted)
1 0 0 1 (sorted)
1 1 1 1 (already sorted)


From truth table we got the boolean algebra equation X=AB Y=A+B So that we can conclude the sortened list of [A,B] is [AB,A+B]

From boolean algebra equation we can design the hardware with logic gate. We can see it only need an AND GATE and an OR GATE.

From simple case we can make it complicated again like first case i mention with 5 elements and for every elements are 2-bits also we can make the device with logic gate.

The question is, any there processing unit in computer architecture that handle sorting like this? Or it's still handled by algorithm (program/software).

If not, will be theres special processor that handle this, if so then sorting is not a problem anymore.

I'm always thinking hardware is powerful than software.

Also i'm wonder any there still time complexity when we take bussiness with boolean algebra?

As far i know we just consider about propagation delay in logic gates which it's come from the transistor technology about time efficiency.

• I know there are sorting VLSI that I passed through in my postgraduate studies 25-30yrs ago, but I honestly didn't follow up the topic mother in research nor in teaching. However, "I think" maybe in MIT courses they say Van Emde Boas Trees was originally arranged this way (working with bits) for such purpose?
– ShAr
Sep 27, 2021 at 8:41
• Oh, and I think all cryptocurrencies mining devices probably contain a HW sorting module inside them for TX selection based on fee for example
– ShAr
Sep 27, 2021 at 8:53
• I don't think that sorting was a problem anyways. The algorithms that do it are so efficient nowadays, that you won't want to waste more reasources on hardware that improves it further. This is only my humble opinion, so please correct me if thats wrong. Sep 27, 2021 at 8:58
• You might be interested in sorting networks. Sep 27, 2021 at 13:56
• The growth in number of comparisons needed by comparison sorts is super-linear in the number of items to order. What do you expect for the number of switches/gates? Try and work out a circuit for ordering three 3-bit values. (In all fairness, things look different in sequential logic.) Sep 28, 2021 at 5:29