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
Can you describe the broader steps of how L2F establishes the tunnel?

Cell splitting  In practice, the distribution of traffic and topographic features is not uniform, and this shows opportunities of capacity enhance. Cells in areas of high usage

Q. What is Retransmission timer? Retransmission timer if an ACK is received previous to the timer goes off - destroy the timer if the timer goes off before ACK a

Multicast An identifier for a set of interfaces (typically belonging to dissimilar nodes). A packet sent to a multicast address is delivered to all interfaces identified by tha

bus topology disadvantage?

Session layer protocols consists of NFS, SQL, RPC, Appletalk Session Protocol (ASP), XWindows, and NetBEUI.

Q. What is Shielded Twisted Pair? - A metal foil or braided-mesh covering encases every pair of insulated conductors to prevent electromagnetic noise called crosstalk - Cros

Network Laye The network  layer provides  communication  between the multiple networks. Whereas the  data link  layer provides the  communication between  two systems on the s

Q. Explain about Error Detection? Data can be corrupted during transmission because of accidents, Storms, sudden increase in electricity and voltage / decrease in signal power

Firewalls After several  security  related internet  newsgroups  started overflowing  with posts it becomes  clear something  hand to done to help  secure  networks. The first