we are using when arrays are usedit is actually necessary for the merge algorithm to create new array to hold the result of the operation at least temporarily in contrastwhen using linked listsit would be possible for merge to work by just changing the reference to the next node this does make for somewhat more confusing codehowever for arraysa suitable merge algorithm would start by creating new array to store the resultsthen repeatedly add the next smallest item into it until one sub-array is finishedthen copy the remainder of the unfinished sub-arrayand finally copy back into amerge(array aint leftint midint rightcreate new array of size right-left+ bcount lcount left rcount mid+ while (lcount <midand (rcount <rightif [lcount< [rcountb[bcount++ [lcount++else [bcount++ [rcount++if lcount mid while rcount <right [bcount++ [rcount++else while lcount <mid [bcount++ [lcount++for bcount bcount right-left+ bcount+ [left+bcountb[bcountit is instructive to compare this with the partition algorithm for quicksort to see exactly where the two sort algorithms differ as with partition the merge algorithm never swaps identical items past each otherand the splitting does not change the ordering at allso the whole mergesort algorithm is stable complexity of mergesort the total number of comparisons needed at each recursion level of mergesort is the number of items needing merging which is ( )and the number of recursions needed to get to the single item level is (log )so the total number of comparisons and its time complexity are (nlog nthis holds for the worst case as well as the average case like quicksortit is possible to speed up mergesort by abandoning the recursive algorithm when the sizes of the sub-collections become small for arrays would once again be suitable size to switch to an algorithm like selection sort note thatwith mergesortfor the special case when only the largest/smallest items need to be found and sortedrather than all nthere is no way to reduce the time complexity in the way it was possible with heapsort and quicksort this is because the ordering of the required items only emerges at the very last stage after the large majority of the comparisons have already been carried out