sorting by merging the idea in the mergesort is to divide an array in halfsort each halfand then use the merge(method to merge the two halves into single sorted array how do you sort each halfthis is about recursionso you probably already know the answeryou divide the half into two quarterssort each of the quartersand merge them to make sorted half similarlyeach pair of ths is merged to make sorted quartereach pair of ths is merged to make sorted thand so on you divide the array again and again until you reach subarray with only one element this is the base caseit' assumed an array with one element is already sorted we've seen that generally something is reduced in size each time recursive method calls itselfand built back up again each time the method returns in mergesort(the range is divided in half each time this method calls itselfand each time it returns it merges two smaller ranges into larger one as mergesort(returns from finding two arrays of one element eachit merges them into sorted array of two elements each pair of resulting -element arrays is then merged into -element array this process continues with larger and larger arrays until the entire array is sorted this is easiest to see when the original array size is power of as shown in figure firstin the bottom half of the arrayrange - and range - are merged into range - of course - and - aren' really rangesthey're only one elementso they are base cases similarly - and - are merged into - then ranges - and - are merged into - in the top half of the array - and - are merged into - - and - are merged into - and - and - are merged into - finallythe top half - and the bottom half - are merged into the complete array - which is now sorted when the array size is not power of arrays of different sizes must be merged for examplefigure shows the situation when the array size is here an array of size must be merged with an array of size to form an array of size firstthe -element ranges - and - are merged into the -element range - then range - is merged with the -element range - this creates -element range - it' merged with the -element range - the process continues until the array is sorted notice that in mergesort we don' merge two separate arrays into third oneas we demonstrated in the merge java program insteadwe merge parts of single array into itself