Find the closed-form solution to the following recurrence relation using the

find the pattern approach. The relation represents the work performed by Quick Sort in the "worst case". Prove your answer is correct using proof by induction.

T(1) = c1

T(n) = T(n 1) + c2n

Sort the following sequence using each of the designated sorting algorithms.

<89, 29, 61, 50, 91, 55, 74, 79, 32, 25>

a. Selection Sort Show the list after each iteration of the outer loop.

b. Insertion Sort Show the list after each iteration of the outer loop.

c. Shell Sort Show the list after each value in the gap sequence. Use the gap sequence <4, 3, 1>.

d. Merge Sort Show the split and merge diagram.

e. Quick Sort Show the result for each list/sub-list after each call to the partition method.