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
(i)  Suppose that frames are 1250 bytes long including 25 bytes of overhead. Also assume that ACK frames are 25 bytes long. a)  Calculate the efficiency of stop-and-wait ARQ in

Lab will require you to create a client and a server that communicate over either message queues, sockets, or a well known fifo. The data passed will be a simple request/response i

Question: a) The cpio utility has three operating modes. What are they? b) The characters of the permission string are broken up into three groups of three characters. Ex

Multiplexing  and De multiplexing Another  critical set of services that are provided by the transport layer is that of application multiplexing and de multiplexing. This featu

Q. Factors effects the quality of image of monitor? Four factors effects the quality of image of monitor:   1.  Phosphor coating: This affects the colour and persistence (Th

Router A router is used to route (transfer) data among two or more same networks. It verifies the next network point to which a data packet should be forwarded. The router is l

Components of the VPN When  using  VPN we incorporate many pieces of a jigsaw puzzle each piece services its own  function to private  the interoperation and the  security  nec

What are the important topologies for networks? BUS topology: In this every computer is directly linked to primary network cable in a single line. Advantages: Inexpensive,

Questions: 1. A 5V Zener diode has a maximum power dissipation of 2W. What is the maximum current that can be safely passed through the device? 2. List three properties of a

Financial Services Today   financial services are totally depended  on computer network. Application includes credit history searchers foreign exchange and  investment service