Illustrate the performance of selection sort algorithm on the following input sequence:

$2,5,16,4,10,23,39,18,26,15$

Provide average case analysis for insertion sort.

Illustrate the performance of heap sort algorithm on the following input sequence:

$2,5,16,4,10,23,39,18,26,15$

Give an $O(nlogk)-$time algorithm to merge k sorted lists into one sorted list, where n

is the total number of elements in all the input lists.