92 Write a recursive method to compute the sum of the first

9.2) Write a recursive method to compute the sum of the first n positive integers. ?

9.9) Explain the three arguments passed to mergeSortHelper() in line 6 of Figure 9-19.

9.11) Is the analysis of merge sort for the best, worst, or average case? Explain. ?

9.13) What is the order of the running time of Quicksort if data is originally in reverse sorted order? What if all the elements are identical?

9.16) Suppose the variable numbers, of type List<Integer>, contains many numbers in no particular order. How can it be sorted in one line of code? (Hint: See the java.util.Collections class in the API.) ?

Figure 9-19. The mergeSortO method returns a new array, rather than modifying data. * kx 2 * Return an array containing the numbers from data, in order from 3*smalest to largest. 5 pubic static int[] mergeSort(int[] data) 6 return mergeSortHeper(data, 0, data.length-1);

Solution

9.2 recursive method to compute sum of n positive integers

9.9

The 3 arguments passed are

data: input data which has to be given to sort function

0:starting index

data.length-1:last index position of array

9.13

If data is originally in reverse and pivot is selected as first element,then the quick sort is in its worst case.

so worst case   running time of quick sort is is \\Theta(n^2) or (n2). If all the elements of quick sort are identical then even if you place the pivot element in any place,you will get worst case complexity