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

Assignment Help:

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


Related Discussions:- sorting circuit along with odd-even merging circuit

Process of skype is a web-based service, Skype is a web-based service which...

Skype is a web-based service which offers cheap and free phone calls. Explain step by step (in terms of networking technology) what really happens from the point when you initiate

Calculate bandwidth needed for voice traffic, The second point to consider ...

The second point to consider is that from each location, some calls are internal to that site and some are going to outside locations. Again, as an approximation, MyCo telecom peop

Explain FDDI media access control, FDDI Media Access Control Unlike CSM...

FDDI Media Access Control Unlike CSMA/CD networks such like Ethernet token-passing networks are deterministic--you are able to calculate the maximum time that will pass before

What do you mean by substitutional ciphers, Q. What do you mean by Substitu...

Q. What do you mean by Substitutional Ciphers? Substitutional Ciphers Monoalphabetic Substitution Polyalphabetic Substitution - Transpositional - character

State synchronous FDDI, Synchronous Synchronous traffic is able to cons...

Synchronous Synchronous traffic is able to consume a portion of the 100 Mbps total bandwidth of an FDDI network while asynchronous traffic can consume the rest. Synchronous

SAN, Case study on SAN Providers and Products available in the market.

Case study on SAN Providers and Products available in the market.

Explain the basic of network properties, Explain the basic of Network Prope...

Explain the basic of Network Properties   The subsequent properties are related with interconnection networks. 1)  Topology: It refers how the nodes a network are systema

Parallel construct in openmp, Parallel Construct The syntax of the para...

Parallel Construct The syntax of the parallel construct is as follows: #pragma omp parallel [set of clauses]  where clause is one of the following:  structured-block if(sca

State the term - netbios and imap, State the term - NetBIOS and IMAP Ne...

State the term - NetBIOS and IMAP NetBIOS: Network Basic Input Output System is an API (applications programming interface) used with other programs to transmit messages betwee

Troubleshooting tcp/ip, I''m having trouble with understanding a diagram fo...

I''m having trouble with understanding a diagram for my assignment

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd