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
An Internet address (IP address) is a unique 32-bit binary number given to a host and used for all interaction with the host. Each packet transmit across an Internet contains the 3

What is a LAN? A LAN is a Local Area Network, within a single building or a specific confined space. LANs typically comprise only one transmission media type like coaxial cable

What is the difference between a JDK and a JVM? JDK is Java Development Kit which is for development purpose and it contains execution environment also. But JVM is purely a

What is the implication of increasing and decreasing subnet Bits?

Q. Why it is essential to have layering in a network? Ans: A computer network is a very complicated system. It becomes very hard to implement as a single entity. The layered ap

Overview Create a prototype web site for the "Computer Superstores" company. Your site should use effective navigation features and demonstrate good structure for  accessibility

Enumerate about the Star networks Comments: 1 - If one connection/station fails the other devices aren't affected 2 - If central hub breaks down, the whole network fail

Q. Show Ethernet Media standard? - The cables and connector specifications utilized to support Ethernet implementations are derived from the EIA/TIA (Electronic Industries Asso


Control Frame: set_successor Station X wants to leave Successor S Predecessor P X sends set_successor frame to P With S as data field P changes its