0
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – ShAr
    Sep 27 at 8:41
  • $\begingroup$ Oh, and I think all cryptocurrencies mining devices probably contain a HW sorting module inside them for TX selection based on fee for example $\endgroup$
    – ShAr
    Sep 27 at 8:53
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    Sep 27 at 8:58
  • $\begingroup$ You might be interested in sorting networks. $\endgroup$ Sep 27 at 13:56
  • $\begingroup$ 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.) $\endgroup$
    – greybeard
    Sep 28 at 5:29
0
$\begingroup$

In the 1960s and even a bit later sorting took up a lot of time. Part of the problem, back then, was the size of main memory (RAM if you like) was small and often the list of records you wanted to sort would not fit in RAM. As a result, the sort algorithm had to read and write the same record several times. Today, just about all files fit in memory.

Today you can sort a large file relatively quickly using a general purpose computer. As a result, I do not see any need for special purpose hardware to help with sorting. However, there could be one or two special cases where it would make sense. I just do not know of any.

$\endgroup$
1
  • $\begingroup$ It's not specifically to help with sorting, but it's usually part of a larger hardwired process where sorting is a necessary preliminary step $\endgroup$
    – ShAr
    Sep 27 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.