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
Some of the ?elds of IP and ICMP datagrams will be ?xed, some will be settable by the application, and others will computed according to the situation. You must set all ?elds of th

Q. Explain Silly window syndrome? When either sending application sends data gradually or receiving application consumes data slowly - Illustration when 1 byte sent 40 bytes

What is Sonet Synchronous Optical Network is a fiber optic technology that can transmit high-speed data audio, used for text and video. Single clock handles timing of transm

Describe the term - Certification Authority The certification is most easily implemented with a custom solution combined with a server, called the Certification Authority (CA).

Mail Access Protocols The e mail  message  are usually  sent to  an email  server that stores received message  in the  recipient   e mail  mailbox.  The user  retrieves messa

Reliability is the probability of success ; where success is defined as compliance to specified requirements. A system or an item is considered reliable if it performs satisfactori

What are the different types of network topologies

Q. What is Retransmission timer? Retransmission timer if an ACK is received previous to the timer goes off - destroy the timer if the timer goes off before ACK a

Explain teh term- Bits and Bitmap Many tiny dots, which are put together to make a picture. Bits are combined to make a graphic image called a bitmap. GIF and JPEG files are

Determine the term - Backend LAN Backend networks are used to interconnect large systems like mainframes, supercomputers, and mass storage devices. The key needs here is for bu