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
Q. Show Data link and Physical vs Subnet? - Data link layer The function of the Data Link Layer is -offers for the control of the physical layer and detects and possib

Inside a device, every address mask is stored as a 32-bit number. When we submit a prefix and an address mask they use a changed form of dotted decimal addressing known CIDR addres

Question 1 Explain the basic communication model with its block diagram Question 2 List and explain the functions of network monitoring Question 3 Explain the get and se

Root DNS Servers A root  server is a serve which  consists of the entire  hierarchy  of servers. A root  server  usually  does not  store any  information  about  domains  but

What are the two types of Transmission Technology available in ccna? Ans) Point - to - Point and Broadcast are the Two types of Transmission Technology available in CCNA

Advantages There are  times when  using  packet filters makes  sense. If the  connections require high  throughput  or the protocols  has proprietary technology that makes  it


Q. How can data to be exchanged between Networks? Internetwork Links in an internetwork

Recognize the command that configures serial0 for PPP encapsulation Ans) Router(config-if)# encapsulation ppp

• This device creates one big collision domain and one large broadcast domain.