entering - base-case return - will sort high half of - entering - base-case return - will merge halves into - return - will sort high half of - entering - will sort low half of - entering - base-case return - will sort high half of - entering - base-case return - will merge halves into - return - will merge halves into - return - thearray= thearray= thearray= this is roughly the same content as would be generated by the mergesort workshop applet if it could sort four items study of this outputand comparison with the code for recmergesort(and figure will reveal the details of the sorting process 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 copied and the number times it must be compared with another data item during 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 seven 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 calculation is thatto sort items requires levelseach of which involves copies level means all copies into the same size subarray in the first levelthere are four -element subarraysin the second levelthere are two -element subarraysand in the third levelthere is one -element subarray each level has elementsso again there are * or copies