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

JAVA, HOW WAS JAVA INVENTED?

HOW WAS JAVA INVENTED?

Microprocesser, explain the bock and pin diagram of 8259 micropocesser

explain the bock and pin diagram of 8259 micropocesser

What is drive, Any data storage device. This having of  your CD-ROM drive, ...

Any data storage device. This having of  your CD-ROM drive, hard disk drive and floppy disk drive.

Two ways of converting a two input nand gate to an inverter, 1)      Short ...

1)      Short both I/Ps of NAND gate & use the gate as an inverter. 2)      Connect any one of the two I/Ps to VCC & use the remaining I/P & use the gate as an inverter.

Explain the difference between fixed and standard effect, Question: (a)...

Question: (a) There are several camera angles that can be used to make a sequence more interesting for a video production project. Explain clearly, using diagrams where appro

Explain about programmer visible registers, Q. Explain about Programmer Vis...

Q. Explain about Programmer Visible Registers? Programmer Visible Registers: These registers can be employed by machine or assembly language programmers to minimize reference

Eight-stage process - conjunctive normal forms, Eight-stage process - Conju...

Eight-stage process - Conjunctive normal forms: Hence we notice the following eight-stage process converts any sentence with CNF as:  1.  Eliminate all arrow connectives by

large block , Given a RAID 3 (bit-interleaved parity) with k disks, how we...

Given a RAID 3 (bit-interleaved parity) with k disks, how well will large block transmits work? How well will it handle a high I/O request rate? Compare the performance to a one di

What are the features of cisc processors, What are the Features of CISC Pro...

What are the Features of CISC Processors The standard features of CISC processors are listed below:  CISC chips have a large amount of dissimilar and complex instructions.

Explain what is a macro and why is it important, Question 1: Spreadshee...

Question 1: Spreadsheet packages are widely used in Business. a) Explain why spreadsheets are so useful. b) Spreadsheet files are sometimes saved for use by other software p

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