( ( ( (pfigure visualization of an execution of merge-sort (continued from figure several invocations are omitted between (mand (nnote the merging of two halves performed in step (pproposition the merge-sort tree associated with an execution of mergesort on sequence of size has height log nwe leave the justification of proposition as simple exercise ( - we will use this proposition to analyze the running time of the merge-sort algorithm having given an overview of merge-sort and an illustration of how it workslet us consider each of the steps of this divide-and-conquer algorithm in more detail dividing sequence of size involves separating it at the element with index / and recursive calls can be started by passing these smaller sequences as parameters the difficult step is combining the two sorted sequences into single sorted sequence thusbefore we present our analysis of merge-sortwe need to say more about how this is done