I was asked to perform merge sort by iterative method. I solved it as follows: I

Question

I was asked to perform merge sort by iterative method. I solved it as follows: I first stored each of the elements of the array given in another array say A. Then I sent entries of A two by two for merging(was given that the function for merging is known and it merged two arrays at a time). This function returned the merged array which I stored in another array B. After I was done with all the elements of A I deleted A and copied each of the entries of B in A.I allocated memories for A and B dynamically. I repeated this for log(n) times and each time I halved the size of A and B. Is my algorithm correct??

Explanation / Answer

I suggest you try to run your algorithm on a few small arrays and see if it works.

Merge sort can be implemented in-place, and the same is true in your case.

Consider the recursive version of merge sort. Apart from calling itself recursively, the only other operation is merge. See if you can make a sequential list of all calls made to merge (with their parameters).

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.