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

ERP, Benefits of implementing ERP

Benefits of implementing ERP

Explain icw, Question 1 What are the drivers behind the convergence betwee...

Question 1 What are the drivers behind the convergence between voice and data networks? Explain them briefly Question 2 Explain the need and functioning of Private ST Netw

What is the size of the variant data type, The Variant data type has a nume...

The Variant data type has a numeric storage size of 16 bytes and can have data up to the range of a Decimal, or a character storage size of 22 bytes (plus string length),and can ke

Participate in grid computing, Different systems that can participate in gr...

Different systems that can participate in grid computing as platform are:  Windows 3.1, 95/98, NT, 2000 XP , DOS, OS/2, , supported by  Intel ( x86); Mac OS  A/UX (Unix)  sup

Elements of composition - line, Line A Line is, on a simple level, a ma...

Line A Line is, on a simple level, a mark connecting 2 points. However, how lines are used in an image is extremely important. By varying the quality of line used in an image,

What are near and far pointers, These days, they're pretty much obsolete; t...

These days, they're pretty much obsolete; they're definitely system-particular. They had to do with 16-bit programming under MS-DOS and perhaps some early on versions of Windows. I

Conversioin of the decimal number 82.67 into octal number , Conversioin of ...

Conversioin of the decimal number 82.67 into Octal number ? Ans. The binary equivalent is (1010010.10101011) 2 of decimal number 82.67. After that convert each 3-bit binary in

When will the current screen processing terminates, When will the current s...

When will the current screen processing terminates? A current screen processing terminates when control reaches either a Leave-screen or the end of PAI.

Explain asynchronous decade counter, Draw the circuit diagram of Asynchrono...

Draw the circuit diagram of Asynchronous decade counter and explain its working. Ans: To  design  a  circuit diagram of decade  asynchronous  counter  initially  we  dr

Nmknl''knl, Ask question bhjjnjnnjnjm#Minimum 100 words accepted#

Ask question bhjjnjnnjnjm#Minimum 100 words accepted#

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