Consider the pseudo-code below for merge sort. Re-write the for-loop as a while

Question

Consider the pseudo-code below for merge sort. Re-write the for-loop as a while loop in the merge sort pseudo-code. (You do not need to show the modified while-loop merge sort.) Then count how many lines need to execute to sort the array [3, 2, 1] for both algorithms. Show some work to receive full (and partial) credit. Only count lines the computer thinks on. Note: for merge sort, do not count the function calls, splits or array creation. Just the number of lines inside the merge function. Also, assume no work needs to be done merging a size 1 and 0 array. (Example: sorting [2, 1] merge = 14 lines.)

Also, find an exact formula for the number of lines needed to be run in both the insertion sort and merge sort pseudo-code. This formula should be for arrays of size n that are in the reverse of sorted (e.g. [8, 7, 6, 5, 4, 3, 2, 1] with n = 8). Give the ranges of n where merge sort performs better than insertion sort. For full points, you cannot use a recursively defined function for merge sort.

TopDownMerge(AL, iBegin, iMiddle, iEnd, BI]) i = iBegin, J = iMiddle ; 1 wnLe unere are elements in the left or right runs.. for (k= iBegin; k

Explanation / Answer

In above question in psedo code of merge sort we have here only merge function which merge two arrays by comparing elements of one array with another.

In function TopDownMerge(....);

we have a single for loop.

Note:Each for loop in a single line contains three statements with it

1. Initialise the variable.

2. Condition check.

3.Increment or Decrement the initialised variable.

So,converting any for loop to while loop it will take extra 2 Lines . One for initialising the variable and another for Incrementing or Decrementing it as condition will be checked inside while(...). Everthing apart from that will remain same in using either of the loops.

In second part of the question as array given is sorted in reverse order so insertion sort will go into its worst time complexity i.e. O(n2) as it will take two for loops one inside another and have to traverse whole array evertime to make insertion of element at right place.Ideally for N elements it will take N(N-1)/2;

whereas, in mergesort we will have time complexity of (nlogn).

Exact lines of code to run Insertion Sort or Merge Sort varies from programmer to programmer either they may use while loop which will increase two more lines in place of each for loop.

The answer claims that 10000 n lg n > 10 n² for "reasonable" n. This is true up to about 14000 elements.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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