10/6/14

Sorting Nets.

Sorting Net sorts a sequence of comparable elements in a time of O(log2 n), where n is number of elements in that sequence.

Sorting Net can be a Parallel Tool & Algorithm that requires n processing units to be effective - a pair of processing units can form a comparator.

There can be more effective solutions as well, for example processing unit with many programmable comparators at it's disposal. Programmable with a 'compare' operation.



Sorting Net Construction Algorithm.
Sorter is Sorting Net, this is recurrential construction.




Sorting Net Construction with expanded recursion, for n = 8.




Sorting Net example, for n = 8.


See also: Merger.

Source: [4].

3 comments:

  1. (EN) even i can see that computers will speed up significiantly in future due to hardware & software upgrade. algorithmics internally as well should improve. there's great potential in ARM Architecture.
    (PL) nawet ja mogę dostrzec że komputery przyspieszą znacząco w przyszłości z powodu dopracowania sprzętu i oprogramowania. algorytmika wewnętrzne też powinna się poprawić. istnieje wielki potencjał w Architekturze ARM.

    ReplyDelete
  2. (EN) MPSS - Multi-Platform Sorting Server should be done using this idea, preferably by author of this blog. Linux version should be included.
    (PL) MPSS - Wieloplatformowy Serwer Sortujący powinien zostać wykonany z wykorzystaniem tej idei, preferuję wykonać to osobiście. Wersja Linuxowa powinna zostać wykonana też.

    ReplyDelete
  3. (EN) Sorting Server will be implemented in Java.
    (PL) Serwer Sortujący zostanie zaimplementowany w Javie.

    ReplyDelete