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
IPv6 The  internet  engineering task force begin  the effort to develop a successor  protocols  to IPv4 in the early  1990 is an internet  layer protocols  for packet  switched

Systolic Array : This interconnection network is a kind of pipelined array architecture and it's intended for multidimensional flow of data. It is used for applying fixed algorithm

In Windows 2000, a domain describes both an administrative boundary and a security boundary for a collection of objects that are relevant to a particular group of users on a networ

Question 1 Explain the following with respect to Data Encoding                     Digital Signaling of Digital Data                     Digital Signal Encoding Techniques Questi

What is CRC The CRC is computed while transmission and appended to output stream as soon as last bit goes out onto wire. If the CRC were in header, it will be necessary to make

Question The circuit in the figure is driven by a 9 mV amplitude signal generator with an output impedance of 2 kW. What is the output voltage amplitude from the circuit in the

Packet Switching In the  packet  switching network  type on specific  path is  used for  data  transfer. Instead the data is chopped up into  small  pieces called packed and s

using binary adition, what is the result of 1010 + 10? Using binary addition, how would you repeatedly increment a number by 2?

It imposes hierarchy and a division of labor between processors. Only one designated processor, the master, controls (in a tightly coupled arrangement) slave processors dedicated t