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
Post Office Protocol and Lightweight Directory Access Protocol POP: Post Office Protocol is a used by mail clients to download messages from a mail server on the Internet. L

What is the difference among TFTP and FTP application layer protocols? The Trivial File Transfer Protocol (TFTP) permits a local host to get files from a remote host but does n

Explain how the lan model be developed The LAN model can be developed incrementally. If LAN is just a long cable. it cannot be brought down by single failure (if servers are re

As the Internet started, the original Classful addressing procedure became a limitation. The IP address space was being terminated because all networks had to select one of three p

what role would you assign for Pentium iii, 500 MHz processor, 256 MB memory, 1o GB hard drive

ETHERNET FIELDS:  In Ethernet fields the preamble and CRC is usually not given in frame. The destination address of each is the broadcast address. There is special value reser

SSK Software Corporation has opened an office in Toledo, Ohio. The office will have a wireless Wi-Fi (WLAN), and a Corporate wired Ethernet LAN. Workstation requirements are as

Most real-life applications are built on top of the UDP and TCP transport protocols. UDP, which stands for User Datagram Protocol, provides the capability of delivering individual

How many ways are there to execute VPN architecture?

How to prevent the data from hackers In order to prevent intruders from entering the house, it is necessary for the house owner to look after the behaviour of internal and exte