For each of the foll owing, show all steps:

(i) Sort the sequence 3, 1, 4, 1, 5, 9, 2, 6, 5 using insertion sort.

(ii) Sort the sequence 142, 543, 123, 65, 453, 879, 572, 434, 111, 242, 811, 102 usingheapsort.

(iii) Sort 3, 1, 4, 1, 5, 9, 2, 6 using mergesort.

(iv) Sort 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 using quicksort with median - of - three partitioning.