chap internal sorting subarrays of size which are in turn merged into subarrays of size and so on we need to avoid having each merge operation require new array with some difficultyan algorithm can be devised that alternates between two arrays much simpler approach is to copy the sorted sublists to the auxiliary array firstand then merge them back to the original array here is complete implementation for mergesort following this approachstatic void mergesort( [ae[tempint lint rint mid ( + )/ /select midpoint if ( =rreturn/list has one element mergesort(atemplmid)/mergesort first half mergesort(atempmid+ )/mergesort second half for (int =li<=ri++/copy subarray to temp temp[ia[ ]/do the merge operation back to int lint mid for (int curr=lcurr<=rcurr++if ( =mid+ /left sublist exhausted [currtemp[ ++]else if ( /right sublist exhausted [currtemp[ ++]else if (temp[ compareto(temp[ ])< /get smaller [currtemp[ ++]else [currtemp[ ++]an optimized mergesort implementation is shown next it reverses the order of the second subarray during the initial copy now the current positions of the two subarrays work inwards from the endsallowing the end of each subarray to act as sentinel for the other unlike the previous implementationno test is needed to check for when one of the two subarrays becomes empty this version also uses insertion sort to sort small subarrays