efficiency of the mergesort as we notedthe mergesort runs in ( *logntime how do we know thislet' see how we can figure out the number of times data item must be copiedand the number of times it must be compared with another data itemduring the course of the algorithm we assume that copying and comparing are the most time-consuming operationsthat the recursive calls and returns don' add much overhead number of copies consider figure each cell below the top line represents an element copied from the array into the workspace adding up all the cells in figure (the numbered stepsshows there are copies necessary to sort items log is so *log equals this shows thatfor the case of itemsthe number of copies is proportional to *log another way to look at this is thatto sort items requires levelseach of which involves copies level means all copies into the same size subarray in the first levelthere are -element subarraysin the second levelthere are -element subarraysand in the third levelthere is -element subarray each level has elementsso again there are * or copies in figure by considering only half the graphyou can see that copies are necessary for an array of items (steps and )and copies are necessary for items similar calculations provide the number of copies necessary for larger arrays table summarizes this information table number of operations when is power of log number of copies into workspace ( *log ntotal copies comparisons max (min ( ( ( ( ( ( ( actuallythe items are not only copied into the workspacethey're also copied back into