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
Simplicity The advantage of this approach is the simplicity  of receiver buffering. The  receiver need not  buffer out of  order packets the sender must maintain the upper an

Explain the technique- Backpressure This technique produces an effect same to backpressure in fluids flowing down a pipe. It includes link-by-link use of flow control in a dire

a)  A host is sending a HTTP request to a HTTP server. In the table below, propose a correct set of source and destination port numbers for segments sent from host to server and fr

This  is one of the models based on PRAM. In this, the processors access the memory location parallel for reading while exclusively for writing operations. In the algorithm which u

Discuss an example of threats in computer software Assume only one attack out of the above list i.e., the virus attack. Though the present anti-virus software solutions can det

Name the factors that affect the performance of the network? a. Number of Users b. Type of transmission medium c. Hardware d. Software

Consider the similar conditions as the last problem, except for the following: what's the minimum possible response time for the 1 Gbps and a 1 Mbps line?  What does the diffrentia

Explain about star topology This topology, obviously, needs a great deal of cabling. This design gives an excellent platform for reconfiguration and trouble-shooting. Changes t

What are the responsibilities of Application Layer? The Application Layer enables the user, whether human or software, to access the network. It gives user interfaces and suppo

What is a Web server? This new model of Client/Server having of thin, portable, "universal" clients that talk to super fat servers. In the easiest form, a web server returns do