Merge sort
“Return” means to group a small sequence into a large sequence, and “merge” means to merge two ordered sequences into one ordered sequence. In my personal understanding, merge sorting is a layer-by-layer merging process.
For example, sort the array array={16, 7, 13, 10, 9, 15, 3, 2, 5, 8, 12, 1, 11, 4, 6, 14}:
Two parts of order make one part of order…two parts of order make one part of order, ultimately order.
Recursive sorting (Merging Sort) is a sorting method implemented using the idea of merging (divide and conquer). Its principle is to assume that the initial sequence has n records, which can be regarded as n ordered subsequences. The length of each subsequence is 1, and then merged in pairs to obtain n/2 lengths of 2 or 1. (extra) ordered subsequence; then merge them two by two,…, repeat until an ordered sequence of length n is obtained. This sorting method becomes a 2-way merge sort.
“Return” part
“Return” means classifying a small sequence into a large sequence. When we implement recursive sorting in a recursive way, we must first divide the large sequence into a reasonable small sequence, and then the process of “returning” begins.
To divide a large sequence into small sequences, we divide two subsequences in the 2-way merge sort, so we need the first and last positions of the left sequence and the right sequence.
In the subsequent “returning” process, I also accompanied the “merging” (sorting), so we also need the head and tail positions of the large sequence. The head and tail of the large sequence coincide with the head and tail of the left sequence and the tail of the right sequence, so no further definition is needed.
That is, we can divide subsequences by head and tail subscripts. In one recursion, we need four data, the head of the large sequence s, the tail of the left sequence of l1, the head of the right sequence of s2, and the tail of the large sequence of l. The recursion end condition can be s1>l2 (Sequence elements cannot be less than 1).
The code is implemented as follows:
public void mergingSort(int[] array) {
MSort(array,0,array.length-1);
}
public static void MSort(int[] array, int s, int l) {
//When the sequence cannot be divided any further, exit directly
if(s>=l) {
return;
}
//End of left sequence
int l1 = (s + l)/2;
//Right sequence first
int s2 = l1 + 1;
//Merge left sequence
MSort(array,s,l1);
//Merge the right sequence
MSort(array,s2,l);
//Sort the [s,l] interval sequence
Merge(array,s,l1,l);
}
The “merge” part
“Merge” means merging two ordered sequences into one ordered sequence. In the “merging” code, after the left and right sequences are merged, the part of the Merge() method that is merged is the part we “merge”.
The four-pointer method can be used to merge two ordered sequences into one ordered sequence, that is, s1 stores the left sequence head subscript, l1 stores the left sequence tail subscript, s2 stores the right sequence head subscript, and l2 stores the right sequence tail subscript.
Because the two sequences are ordered, the subscripted elements of s1 and s2 are the minimum values of the two sequences. Compare array[s1] and array[s2], store the smaller one in the additional array space, and then subscript the position + +, so that s1 or s2 always points to the minimum value of the unsorted parts of the two sequences, repeat this process until one of the sequences is traversed.
After one sequence has been traversed, there may be unsorted elements in the other sequence. Because the remaining elements are already ordered and are definitely larger than the sorted elements in the extra space, they can be directly inserted into the extra space in order.
Code:
public static void Merge(int[] array, int s, int mid, int l) {
//Create an array to store the sorted sequence, and finally copy it back to the original sequence
int[] tmpArr = new int[(l-s) + 1];
//The beginning and end of the sequence
int s1 = s;
int l2 = l;
int l1 = mid;
int s2 = l1 + 1;
int i = 0;
//Four pointer sorting
while(s1 <= l1 & amp; & amp; s2 <= l2) {
if(array[s1] <= array[s2]) {
tmpArr[i + + ] = array[s1 + + ];
} else {
tmpArr[i + + ] = array[s2 + + ];
}
}
//Insert the remaining elements of the left or right sequence into tmpArr
while(s1 <= l1) {
tmpArr[i + + ] = array[s1 + + ];
}
while(s2 <= l2) {
tmpArr[i + + ] = array[s2 + + ];
}
//Copy the sorted array back to array
for(i = 0; i < tmpArr.length; i + + ) {
array[s + i] = tmpArr[i];
}
}
Merge sort complexity analysis
The time complexity of merge sorting. One merge requires merging adjacent ordered sequences of length h in array[1]~array[n] in pairs. And put the results into tmpArr[1]~tmpArr[n], which requires scanning all the records in the sequence to be sorted, so it takes O(n) time. From the depth of the complete binary tree, it can be seen that the entire merge sort needs to be carried out [logn] times, therefore, the total time complexity is O(nlogn), and this is the best, worst and average time performance of the merge sort algorithm.
Since merge sort requires the same amount of storage space as the original record sequence to store the merged results during the merging process, the space complexity is O(n).
In addition, after careful study of the code, we found that there is an if(SR[i]
Non-recursive implementation
The non-recursive implementation is very simple, the focus is on determining the beginning and end of the subsequence.
The method is to define an integer (int) gap to represent the number of elements in each group of sequences, and merge according to the groups divided by the gap. The division of large and small sequences is achieved by gap*=2.
public static void MSort(int[] array, int s, int l) {
if(array .length == 0) return;
int gap = 1;
//Cannot exceed its own quantity
while(gap < array.length) {
for(int i = 0; i < array.length; i = i + gap*2) {
//First left
int s1 = i;
//Left tail
int mid = i + gap-1;
//right tail
int l2 = mid + gap;
//The sequence cannot cross the boundary
if(mid >= array.length) {
mid = array.length-1;
}
if(l2 >= array.length) {
l2 = array.length-1;
}
Merge(array,s1,mid,l2);
}
gap*=2;
}
}
The blogger is new to Java. The support of every comrade will give the blogger great motivation. If you have any questions or find any errors, you are welcome to communicate in the comment area “ψ(｀?′)ψ
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56862 people are learning the system