Merge sort is an effective sorting algorithm based on the merge operation. It merges ordered subsequences to obtain a completely ordered sequence. This algorithm uses the divide and conquer method. The merge operation, also called the merge algorithm, refers to the method of merging two sequential sequences into one sequential sequence.
Merge sort (MERGE-SORT) is an effective sorting algorithm based on merge operations. The algorithm uses the divide and conquer method ( Divide and Conquer) is a very typical application.
Merge the ordered subsequences to obtain a completely ordered sequence; that is, first make each subsequence orderly, and then make the subsequence segments orderly.
If two ordered lists are merged into one ordered list, it is called a two-way merge. Merge sort is a stable sorting method.
The merge operation (merge), also called the merge algorithm, refers to the method of merging two sequential sequences into one sequential sequence.
Example
Suppose there is a sequence {6, 202, 100, 301, 38, 8, 1}
Initial state: 6,202,100,301,38,8,1
After the first merge: {6,202}, {100,301}, {8,38}, {1}, number of comparisons: 3;
After the second merge: {6,100,202,301} , {1,8,38}, number of comparisons: 4;
After the third merge: {1,6,8,38,100,202,301}, number of comparisons: 4;
Total comparison The number of times is: 3 4 4=11;
The reverse number is 14;
For more related knowledge, please visit PHP Chinese website! !
The above is the detailed content of What does merge sort mean?. For more information, please follow other related articles on the PHP Chinese website!