Merge sorting method is to merge two (or more) ordered tables into a new ordered table. One disadvantage of merge sorting is that it requires memory to have another array of size equal to the number of data items. If the initial array takes up almost the entire memory, then merge sorting will not work, but if there is enough space, merge sorting will be a good choice.
Assume that the sequence to be sorted:
4 3 7 9 2 8 6
Let’s talk about the idea first. The central idea of combining sorting is to merge two already sorted sequences into one sorted sequence.
The above sequence can be divided into:
4 3 7 9
and
2 8 6
These two sequences are then sorted separately: the result is:
Set to sequence A, and sequence B,
3 4 7 9
2 6 8
Merge the above two sequences into a sorted sequence:
The specific ideas for merger are:
Set two position indicators, pointing to the starting position of sequence A and sequence B respectively: red is the indicator pointing position:
3 4 7 9
2 6 8
Compare the values of the elements pointed to by the two indicators, insert the smaller one into a new array, such as sequence C, and move the corresponding indicator one by one:
The result is:
3 4 7 9
2 6 8
The sequence C formed: an element has been inserted, the smaller element 2 just now.
2
Then compare the elements pointed to by the indicator in sequence A and sequence B again: put the small one into sequence C, move the corresponding pointer, and the result is:
3 4 7 9
2 6 8
2 3
And so on, iteratively executes until a certain indicator in sequence A or sequence B has been moved to the end of the array. For example:
After multiple comparisons, sequence B has moved the indicator to the end of the sequence (after the last element).
3 4 7 9
2 6 8
2 3 4 6 7 8
Then insert the unused sequence, where all the remaining elements in sequence A are inserted behind sequence C, and only one 9 is left. After inserting it into sequence C:
Sequence C results:
2 3 4 5 6 7 8 9
This implements the operation of combining two ordered sequences into one ordered sequence.
Let's first look at the merged php code:
/**
* Combine two ordered numbers into an ordered array
* @param $arrA,
* @param $arrB,
* @reutrn array merge good array
*/
function mergeArray($arrA, $arrB) {
$a_i = $b_i = 0;//Set two start position marks $a_len = count($arrA);
$b_len = count($arrB);
while($a_i<$a_len && $b_i<$b_len) {
//When neither array A nor array B crosses the boundary if($arrA[$a_i] < $arrB[$b_i]) {
$arrC[] = $arrA[$a_i++];
} else {
$arrC[] = $arrB[$b_i++];
}
}
//Judge whether all the elements in array A are used up. If not, insert all of them into array C: while($a_i < $a_len) {
$arrC[] = $arrA[$a_i++];
}
//Judge whether all the elements in array B are used up. If not, insert all of them into array C: while($b_i < $b_len) {
$arrC[] = $arrB[$b_i++];
}
return $arrC;
}
After the above analysis and the implementation of the program, it is not difficult to find that the time for merging the sorted sequences should be linear, that is, at most, N-1 comparisons will occur, where N is the sum of all elements.
Through the above description, we implement the process of summing and merge two sorted arrays.
At this time, you may have questions, what does this have to do with sorting the entire sequence? Or how can you get the first two sorted subsequences?
Next, let’s describe the following: What is merge sorting, and then see how the above merge and merge sorting relationship is:
You might as well think about it. When we need to sort the following array, can we first sort the first half of the array and the second half of the array separately, and then merge the sorted results?
For example: array to be sorted:
4 3 7 9 2 8 6
First divide it into 2 parts:
4 3 7 9
2 8 6
Consider the first half and the second half as a sequence, and merge again (that is, split, sort, merge)
It will become:
forward:
4 3
7 9
back:
2 8
6
Similarly, each self-sequence is merged and sorted again (split, sort, merge).
When there is only one element (length is 1) in the split subsequence, then the sequence does not need to be split, it is a sorted array. Then merge this sequence with other sequences, and finally merge everything into a complete sorted array.
Program implementation:
Through the above description, you should think that you can use recursive programs to implement this programming:
To implement this program, you may need to solve the following problems:
How to split an array:
Set two indicators, one pointing to the array starts as $left, and the other pointing to the last element of the array $right:
4 3 7 9 2 8 6
Then determine whether $left is less than $right. If it is less than, it means that the number of elements in this sequence is greater than one, and then split it into two arrays. The way to split it is to generate an intermediate indicator $center, with the value $left + $right /2 divisor. The result is: 3, and then divide $left to $center into a group, and $center+1 to $right into a group:
4 3 7 9
2 8 6
Next, recursively use $left, $center, $center+1, and $right as left and right indicators of two sequences to operate. Know that there is an element $left==$right in the array. Then merge the array as above:
/**
* mergeSort merge sort
* is a driver function that starts the recursive function
* @param &$arr array Array to sort
*/
function mergeSort(&$arr) {
$len = count($arr);//Finding the array length
mSort($arr, 0, $len-1);
}
/**
* The actual program to implement merge sorting
* @param &$arr array The array to be sorted
* @param $left int Sublease value of subsequence
* @param $right int Sub-right value of sub-sequence
*/
function mSort(&$arr, $left, $right) {
if($left < $right) {
//Indicate that there is an extra element in the sub-sequence, then it needs to be split, sorted separately, and merged. //Calculate the position of the split, length/2 to complete $center = floor(($left+$right) / 2);
//The recursive call sorts the left side again: mSort($arr, $left, $center);
//Recursive call sorts the right side again mSort($arr, $center+1, $right);
//Merge sorting results mergeArray($arr, $left, $center, $right);
}
}
/**
* Combine two ordered numbers into an ordered array
* @param &$arr, all elements to be sorted
* @param $left, the beginning subscript of sorting subarray A
* @param $center, the middle subscript of sorting subarray A and sorting subarray B, that is, the end subscript of array A
* @param $right, the end subscript of sorting subarray B (start is $center+1)
*/
function mergeArray(&$arr, $left, $center, $right) {
//Set two start position marks $a_i = $left;
$b_i = $center+1;
while($a_i<=$center && $b_i<=$right) {
//When neither array A nor array B crosses the boundary if($arr[$a_i] < $arr[$b_i]) {
$temp[] = $arr[$a_i++];
} else {
$temp[] = $arr[$b_i++];
}
}
//Judge whether all the elements in array A are used up. If not, insert all of them into array C: while($a_i <= $center) {
$temp[] = $arr[$a_i++];
}
//Judge whether all the elements in array B are used up. If not, insert all of them into array C: while($b_i <= $right) {
$temp[] = $arr[$b_i++];
}
//Write the sorted part in $arrC into $arr: for($i=0, $len=count($temp); $i<$len; $i++) {
$arr[$left+$i] = $temp[$i];
}
}
//do some test:
$arr = array(4, 7, 6, 3, 9, 5, 8);
mergeSort($arr);
print_r($arr);
Note that the above code uses reference passing in the arrays sorted to save space.
Moreover, the method of merging the array has also been relatively modified to save space, and all operations are put on $arr to save resources by reference.
OK, the above code completes the merge sorting, and the time complexity of merge sorting is O(N*LogN) and the efficiency is still quite objective.
Besides, the central idea of the merge sorting algorithm is a method of decomposing a complex problem into similar small problems, then decomposing the small problem into smaller problems until it can be solved immediately, and then combining the results obtained by the decomposition. This idea is described in an idiom as breaking the whole into the zero. In computer science, there is a major called divide-and-treat strategy (divide-and-treatment). Score means that big problems turn into small problems, and treatment means that small results merge into big results.
Dividing and consolidation strategies are the basis of many funny algorithms. When we discuss quick sorting, we will also use dividing and consolidation strategies.
Finally, let’s briefly talk about this algorithm, although this algorithm reaches O(NLogN) in terms of time complexity. But there is still a small problem. When merging two arrays, if the total number of elements of the array is N, then we need to open up a space of the same size to save the merged data (that is, the $temp array in mergeArray), and we also need to copy the data to $temp and $arr, so some resources will be wasted. Therefore, it is relatively rarely used in actual sorting.