merging two sorted sequences can be done in linear time as we mentioned earlierwe analyze the merge-sort algorithm by referring to the merge-sort tree (recall figures through we call the time spent at node of the running time of the recursive call associated with vexcluding the time taken waiting for the recursive calls associated with the children of to terminate in other wordsthe time spent at node includes the running times of the divide and conquer stepsbut excludes the running time of the recur step we have already observed that the details of the divide step are straightforwardthis step runs in time proportional to the size of the sequence for in additionas discussed abovethe conquer stepwhich consists of merging two sorted subsequencesalso takes linear timeindependent of whether we are dealing with arrays or linked lists that isletting denote the depth of node vthe time spent at node is ( / )since the size of the sequence handled by the recursive call associated with is equal to / looking at the tree more globallyas shown in figure we see thatgiven our definition of "time spent at node,the running time of merge-sort is equal to the sum of the times spent at the nodes of observe that has exactly nodes at depth this simple observation has an important consequencefor it implies that the overall time spent at all the nodes of at depth is ( / )which is (nby proposition the height of is logn thussince the time spent at each of the logn levels of is ( )we have the following resultproposition algorithm merge-sort sorts sequence of size in (nlogntimeassuming two elements of can be compared in ( time in other wordsthe merge-sort algorithm asymptotically matches the fast running time of the heap-sort algorithm figure visual time analysis of the merge-sort tree each node is shown labeled with the size of its subproblem