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
What is Unacknowledged connectionless service This service is a datagram-style service. It is a very simple service that does not involve any of the flow- and error-control mec

WHAT IS NETWORK???

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

Explain about the Database Management Intranet This type of Intranet provides everyone in an organisation with the capability to maintain a "real-time" interactive database.


What is the difference between routable and non- routable protocols? Ans) Routable protocols can work with a router and can be used to build huge networks. Non-Routable protocol

Question 1: a. What is xDSL and enumerate the benefit of such a technology? b. Name some of the typical applications of xDSL and the different types and standards of xDSL.

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

The LAN switch copies the whole frame into its onboard buffers and then looks up the destination address in its forwarding, or switching, table and verifies the outgoing interface

Connectionless Multiplexing  and De multiplexing Java program running in a host can create a UDP socket  with the  line Datagram's socket my socket =  new datagram's socket