Analysis of merge sort, Computer Engineering

Assignment Help:

i) The width of the sorting + merging circuit is equivalent to maximum number of devices needed in a phase is O(n/2). As in the above diagram maximum number of devices for a given phase is 4 that is 8/2 or n/2. 

ii) The circuit comprises two sorting circuits for sorting sequences of length n/2 and afterwards one merging circuit for merging of two sorted sub sequences (see phase 4th  in above figure). Let functions Tm and Ts signify 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), 

 Therefore, Ts (n) is equal to O (log2 n).

2264_Analysis of Merge Sort.png

Figure: Sorting + Merging Circuit


Related Discussions:- Analysis of merge sort

Explain the differences of casex and casez, Explain the differences of case...

Explain the differences of casex and casez over the case statement? casex operator has to be used when both high impedance value (z) and unknown (x) in any bit  has  to  be  t

How does multiplexer know which line to select, How does multiplexer know w...

How does multiplexer know which line to select? This is managed by select lines. The select lines provide communication among different components of a computer. Now let's see

Describe about immediate addressing mode, Q. Describe about Immediate Addre...

Q. Describe about Immediate Addressing mode? When an operand is interpreted as an immediate value for example LOAD IMMEDIATE 7 it is actual value 7 which is put in CPU register

Carry save addition and generated and propagate function, Explain carry sav...

Explain carry save addition (CSA) process. Ans: Instead of allowing the carries ripple along the rows, they can be saved and then introduced into the next roe at the right wei

What is home banking, Home Banking: E-commerce is used in Home Banking ...

Home Banking: E-commerce is used in Home Banking as single call or single click. Online banking (Internet banking) is a term used for performing transactions, payments etc. ove

Operating systems, Consider the state transition diagram of Figure 3.9b . S...

Consider the state transition diagram of Figure 3.9b . Suppose that it is time for the OS to dispatch a process and that there are processes in both the Ready state and the Ready/S

Explain the access methods used in lans, Explain the access methods used in...

Explain the access methods used in LANs. Access methods utilized in LAN: i. Switched access: this is used in LANs which are assigned around CBXs. Electronic switching

Explain subscriber access to strowger systems, What are the basic approache...

What are the basic approaches to the design of subscriber access to Strowger systems? Describe them. A step by step switching system has three main parts as demonstrated in fig

Congestion in network layer, explain different types of congestion in netwo...

explain different types of congestion in network layer?

The information on the current screen, How do you find the information on t...

How do you find the information on the current screen? The information on the present screen can be found by SYSTEM ? STATUS command from any menu.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd