Untitled

Prof. Ignore was writing Merge sort algorithm. He lost his memory in between and wrote a wrong statement of the algorithm (the statement is underlined). However, he is curious about the effects of this faulty algorithm. He asks you to derive the output of the following faulty Merge sort on the input array a (19, 7, 15, 12, 16, 18, 4, 11, 13) and find the output. Write the output array only as your answer MA (5 Marks) Note: Partial marking will not be done for this question. KOM MERGE SORT (arr, beg, end) if beg end then mid (beg end)/2 MERGE SORT (arr, beg, mid) MERGE SORT (arr, mid + 1, end) MERGE (arr, beg, mid, end) END MERGE SORT 12 Merge (arr, beg, mid, end) n1 mid - beg + 1 n2 end mid



end mid LeftArray[nl] //temporary array RightArray [n2] //temporary array for i 0 to nl do LeftArray[i] arr [beg + i] for j = 0 to n2 do RightArray[j]- arr[mid + 1 + j] 0 /* initial index of first sub-array */ 0 / initial index of second sub-array */ k beg /* initial index of merged sub-array */ while i < nl and j n2 do if (LeftArray[i] mod 2 == 0) then //in place of LeftArray[1] <= RightArray[j] else arr[k] LeftArray[i] i i + 1 arr[k] RightArray[j] end if end while while i < nl do arr[k]- LeftArray[i] i-i+l k k + end while while j < n2 do arr[k] RightArray[j] jj +1 kk+ 1 end while