sorting circuit along with odd-even merging circuit, Computer Networking

As we previously know, the merge sort algorithm needs two circuits, i.e. one for merging and second for sorting the sequences. Thus, the sorting circuit has been derived from the above-discussed merging circuit. The useful steps followed by the circuit are given below:

i) The given input series of length n is separated into two sub-sequences of length n/2 each.

ii) The two sub series are recursively sorted.

iii) The two sorted sub series are merged (n/2,n/2) using a merging circuit in order to finally get the sorted series of length n.

Now, let us take an instance for sorting the n numbers say 4,2,10,12 8,7,6,9. The circuit of sorting + merging given series is illustrated in Figure.

Analysis of Merge Sort

i)          The width of the sorting + merging circuit is equivalent to the maximum number of devices needs in a stage is O (n/2). As in the above figure the maximum number of devices for a given stage is 4 which is n/2or8/2.

ii)      The circuit has two sorting circuits for sorting series of length n/2 and after that one merging circuit for merging of the two sorted sub series (see stage 4th in the above figure). Let the functions Tm and Ts denote the time complexity of merging and sorting in terms of its depth.

The Ts can be calculated as follows: Ts (n) =Ts (n/2) + Tm (n/2) Ts (n) =Ts (n/2) + log (n/2),

Thus, Ts (n) is equal to O(log2 n).

640_Sorting + Merging Circuit.png

                                                                   Sorting + Merging Circuit

Posted Date: 3/2/2013 6:48:10 AM | Location : United States







Related Discussions:- sorting circuit along with odd-even merging circuit, Assignment Help, Ask Question on sorting circuit along with odd-even merging circuit, Get Answer, Expert's Help, sorting circuit along with odd-even merging circuit Discussions

Write discussion on sorting circuit along with odd-even merging circuit
Your posts are moderated
Related Questions
Network  Control  protocols ( NCP) The first  ARPANET  networking protocols  was named  simply the network  control protocols in 1970,and  was created by  created by  network

Routing Table A routing  table has columns  for at  three types o information  the network  ID  the cost  and the  ID of the  next  router. The  network  ID is the final  desti

What is Bit Stuffing? Bit stuffing is the process of adding one extra 0 whenever five consecutive is follow a 0 in the data, so that the receiver does not mistake the pattern 0

Describe the concept of successor and feasible successor?

- Light source is LED (light-emitting diode) or a laser - LEDs are cheaper however not as precise (unfocused) limited to short-distance use - Lasers is able to have a narrow

Matric define as Formula of path selection

Electronic Cheques   Another mechanism for Internet payment is electronic cheques. With electronic cheques, the payer (either an individual consumer or a business) instructs his

Explain how the lan model be developed The LAN model can be developed incrementally. If LAN is just a long cable. it cannot be brought down by single failure (if servers are re

Butterfly permutation This permutation is getting by interchanging the important significant bit in address with smallest significant bit.

How to protect computer Hardware by threats The first component in the computer system vulnerable to attacks or threats, and most important to be protected, is the hardware.