Eight kinds of ordering relationships:

First, basic ideas

Merge sort merges two ordered lists to form a new ordered list, that is, the sequence to be sorted is divided into several sub-sequences, each sequence is ordered, and then the ordered sub-sequence is merged into the whole ordered sequence.

Second, the instance

Third, implementation process analysis

Merge sort after two decomposition, the core of the merger, decomposition, due to the merger of sequence must be orderly sequence, how to choose, constantly wake the decomposition, decomposition to into a sequence of one element, it must be an ordered sequence of this draws on recursion, tear open a source sequence into an orderly sequence And then there is a merger.

3.1 Merge: merge two ordered sequences into one ordered sequence

First look at the merge part, provide a concatenated subsequence, set to the ordered array data[] left… Center center… A right merge is a merge of two subsequences. Create a temporary array to store the elements of this sequence, the length of two subsequences:

int tmpArr = new int[right-left+1];
Copy the code

Defines a variable to hold an index stored in a temporary array

int third = left;
Copy the code

Define a variable as the index record for the second element

int tmp=left;
int mid = center+1;
Copy the code

Since both subsequences are ordered, the elements of each sequence are compared, and the smaller elements are stored in a temporary array.

If (data[left]<=data[mid]){tmpArr[third++]=data[left++]; }else{ tmpArr[third++]=data[mid++]; }}Copy the code

The comparison of two sequences ends with the comparison of elements in one sequence. It is not known whether the comparison of elements in the other sequence is complete, so the remaining elements in the sequence need to be stored in a temporary array

while(mid <=right) {
    tmpArr[third++]=data[mid++];
}
while(left <= center) {
    tmpArr[third++]=data[left++];
}
Copy the code

When we’re done, we’re going to store the elements of the temporary array into the original array

for(i=0; i<tmpArr.length; i++) {
    data[tmp++]=tmpArr[i++];
}
Copy the code

3.2 Ideas of decomposition and divide-and-conquer

In the diagram above, you can see that by constantly splitting the array to be sorted, finally splitting an element, defining center, splitting the sequence into two subsequences, sorting the two molecular sequences, and (since the sorting is performed recursively) splitting the sequence into individual elements, Only call merger() last for merger.

/** * * @param data * @param left * @param right */ public void sort(int[] data, int left, Int center=(left+right)/2; int center=(left+right)/2; // Sort the left array recursively (data,left,center); // Sort (data,center+1,right); / / merge the merge (data, left, center, right); }}Copy the code

Fourth, Java implementation

package com.chb.sort; import java.util.Arrays; Public class mergingSort {int a [] = 49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51 {}; public mergingSort(){ sort(a,0,a.length-1); for(int i=0; i<a.length; i++) System.out.println(a[i]); } /** * * @param data * @param left * @param right */ public void sort(int[] data, int left, Int center=(left+right)/2; int center=(left+right)/2; // Sort the left array recursively (data,left,center); // Sort (data,center+1,right); / / merge the merge (data, left, center, right); }} public void merge(int[] data, int[] data, int[] data, int[] data, int[] data, int left, int center, int right) { int [] tmpArr=new int[data.length]; int mid=center+1; Int third=left; int tmp=left; If (data[left]<=data[mid]){tmpArr[third++]=data[left++]; }else{ tmpArr[third++]=data[mid++]; While (mid<=right){tmpArr[third++]=data[mid++]; } while(left<=center){ tmpArr[third++]=data[left++]; } // Copy the contents of the intermediate array back to the original array while(TMP <=right){data[TMP]=tmpArr[TMP ++]; } System.out.println(Arrays.toString(data)); }}Copy the code