Merge Sort is an effective and stable sorting algorithm based on merge operations. This algorithm is a very typical application of the divide and conquer method .
Merge sort combines two ordered subsequences to obtain a completely ordered sequence, that is, first make each subsequence sorted, and then make the subsequence segments sorted. If two ordered lists are merged into one ordered list, we call it a two-way merge .
The speed of merge sort is second only to quick sort, and the time complexity is O(nlogn). The splitting process uses the idea of dichotomy, which is a recursive process. In order to reduce the problem of continuously opening up space during the recursive process, we can first open up a temporary space before merging and sorting, and use this space uniformly during the recursive process. Just merge.
For example:
importjava.util.Arrays;publicclassMain{publicstaticvoidmain(String[]args){int[]arr=newint[]{86,23,7,45,19,10};intleft=0;intright=arr.length-1; int[]tem=Arrays.copyOf(arr,arr.length);print(arr);mergeSort(arr,left,r ight,tem);print(arr);}publicstaticvoidmergeSort(int[]arr,intleft,intright,int[]tem){if(right-left<1){return;}intmid=left+(right-left)/2 ;mergeSort(arr,left,mid,tem);mergeSort(arr,mid+1,right,tem);merge(arr,left,mid ,right,tem);}privatestaticvoidmerge(int[]arr,intleft,intmid,intright,int[]tem){intindex=0;intl=left,r=mid+ 1;while(l<=mid&&r<=right){if(arr[l]<arr[r]){tem[index++]=arr[l++];}else{tem[index++]=arr[r++];} }while(l<=mi d){tem[index++]=arr[l++];}while(r<=right){tem[index++]=arr[r++];}for(inti=0;i<(right-left+1);i++ ){arr[left +i]=tem[i];}}privatestaticvoidprint(int[]arr){for(inti:arr){System.out.print(i+t);}System.out.println();}} The running results are as follows:
8623745191071019234586