algorithm

Answer 1

both the oprtions B and C are correct

Comments

Thanks for answering the question, but it would have been better if you had provided a detailed reason.

Answer 2

A) Merge sort processes elements by diving and merging. It does not always perform more swaps than comparison. In fact, standard merge sort moves elements to another array rather than performing traditional element swaps. So A is False.

B) The total number of comparisons in the partition process depends entirely on how evenly the array is partitioned. In best case, array can be partitioned into two equal halves, creating balanced tree that require very few total comparisons (O(nlogn)).In worst case, the array may get split unevenly that forces the entire array to compared over and over again.(O($n^{2}$)). So B is False.

Note that if single partition routine is performed, then the number of comparisons remains same in best and worst case.

C) Merge sort uses an extra array to combine two subarrays. So it is not an inplace algorithm. Quicksort just picks a pivot and place it into its right position (no extra space). So C is True.

 

Comments

To partition an array of size n, you have to compare every single element against the pivot to see which side it belongs on. That always takes exactly n - 1 comparisons, whether that split ends up being a perfect best-case or a terrible worst-case. The partition step itself does the exact same amount of work either way.