the running time of merge-sort now that we have given the details of the merge-sort algorithmin both its arraybased and list-based versionsand we have analyzed the running time ofthe crucial merge algorithm used in the conquer steplet us analyze the running time of the entire merge-sort algorithmassuming it is given an input sequence of elements for simplicitywe restrict our attention to the case where is power of we leave it to an exercise ( - to show that the result of our analysis also holds when is not power of as we did in the analysis of the merge algorithmwe assume that the input sequence and the auxiliary sequences and created by each recursive call of