$3.$Sort the sequence $8,1,4,1,5,9,2,6,5$ by using

a$.$ Insertion sort

b$.$ Mergesort

c$.$ Quicksort, with the middle element as pivot and no cutoff $($show

all steps$)$