Table of Contents
1. Principle of merge sort
1.1 Two-way merge sort execution process
2. Code analysis
2.1 Code design
3. Performance analysis
4. Non-recursive version
1. Principle of merge sort
The Chinese meaning of the word “merge” is to merge or merge, and the definition in data structure is to combine two or more ordered lists into a new ordered list.
Merging Sort is a sorting method implemented using the idea of merging. Its principle is to assume that the initial sequence contains n records, which can be regarded as n ordered subsequences, each subsequence has a length of 1, and then merged in pairs to obtain [n/2] (
1.1 Two-way merge sort execution process
Original sequence: 49 38 65 97 76 13 27
(1) Consider the original sequence as 7 subsequences containing only one keyword. Obviously these subsequences are all ordered.
Subsequence 1:49; Subsequence 2:38; Subsequence 3:65; Subsequence 4:97; Subsequence 5:76; Subsequence 6:13; Subsequence 7:27
(2) Merge two by two to form several ordered binary groups, that is, 49 and 38 are merged into {38 49}, 65 and 97 are merged into {65 97}, and 76 and 13 are merged into It becomes {13 76}, 27 has no merged objects, and remains {27} as it is. The first two-way merge sort is completed, and the results are as follows:
{38 49}, {65 97}, {13 76}, {27}
(3) Then treat this sequence as a number of tuple subsequences
Subsequence 1: 38 49; Subsequence 2: 65 97; Subsequence 3: 13 76; Subsequence 4: 27;
The length of the last subsequence may be 1 or 2.
(4) Continue merging two by two to form several Ordered Quadruples (Similarly, there may not be 4 keywords in the final subsequence), that is, {38 49} and {65 97} are merged Forming {38 49 65 97}, {13 76} and {27} merged to form {13 27 76}. The second pass of two-way merge sorting is completed, and the results are as follows:
{38 49 65 97}, {13 27 76}
(5) In the end, there are only two subsequences. Perform another merge to complete the entire two-way merge sort. The results are as follows:
13 27 38 49 65 76 97
2. Code Analysis
Let’s see if you have any ideas first!
3,2,1 Let’s start my show hahaha!
See illustration:
2.1 Code Design
How do we design a method based on the diagram?
I plan to write the decomposition function as a method and the merging function as a method. The specific implementation is as follows:
public static void mergeSort1(int[] array){
mergeSortDivide(array,0, array.length - 1);
}
//break down
private static void mergeSortDivide(int[] array,int left,int right){
//Termination condition: left > right
while(left >= right){
return;
}
int mid = (left + right)/2;
//Recursive left subsequence
mergeSortDivide(array,left,mid);
//recursive right subsequence
mergeSortDivide(array,mid + 1,right);
//merge
merge(array,left,right,mid);
}
//merge
private static void merge(int[] array,int start,int end,int mid){
//The left subsequence starts from start
int s1 = start;
//The right subsequence starts from mid + 1
int s2 = mid + 1;
//Create a new array as a copy array
int[] tmp = new int[end - start + 1];
//k represents the element subscript of the intermediate array
int k = 0;
//Start comparison
while(s1 <= mid & amp; & amp; s2 <= end){
if(array[s1] <= array[s2]){
//Assign small value to tmp[k]
//Friends, you can think about this: Why can't you write array[s2] <= array[s1] first?
//Wait for my analysis below!
tmp[k + + ] = array[s1 + + ];
} else{//array[s2] <= array[s1]
tmp[k + + ] = array[s2 + + ];
}
}
//There are remaining arrays
//Left subsequence
while(s1 <= mid){
tmp[k + + ] = array[s1 + + ];
}
//right subsequence
while(s2 <= end){
tmp[k + + ] = array[s2 + + ];
}
//Assign the value of the tmp array to the array array
for(int i = 0;i<tmp.length;i + + ){
array[i + start] = tmp[i];
}
}
Answer the question: Why can’t you write array[s2] <= array[s1] first?
Answer: Merge sort is stable. If you write array[s2] <= array[s1] first, then if the elements starting from s2 are equal to the elements starting from s1, for example: 1<=1, then the 1 that should be at the back will be moved to the front, causing this The merge sort implemented by this code is unstable!
3. Performance Analysis
| Time complexity | Space complexity |
| O(n*log(n)) | O(n) |
4. Non-recursive version
The version above is the recursive version, next is the non-recursive version.
private static void merge(int[] array,int start,int end,int mid) {
int s1 = start;
//int e1 = mid;
int s2 = mid + 1;
//int e2 = end;
int[] tmp = new int[end-start + 1];
int k = 0; //Subscript of tmp array
while (s1 <= mid & amp; & amp; s2 <= end) {
if(array[s1] <= array[s2]) {
tmp[k + + ] = array[s1 + + ];
}else {
tmp[k + + ] = array[s2 + + ];
}
}
while (s1 <= mid) {
tmp[k + + ] = array[s1 + + ];
}
while (s2 <= end) {
tmp[k + + ] = array[s2 + + ];
}
for (int i = 0; i < tmp.length; i + + ) {
array[i + start] = tmp[i];
}
}
public static void mergeSort(int[] array) {
int gap = 1;
while (gap < array.length) {
// i + = gap * 2 When the current gap group is in the current gap group, sort the next group
for (int i = 0; i < array.length; i + = gap * 2) {
int left = i;
int mid = left + gap-1;//It may cross the boundary
if(mid >= array.length) {
mid = array.length-1;
}
int right = mid + gap;//may cross the boundary
if(right>= array.length) {
right = array.length-1;
}
merge(array,left,right,mid);
}
//Currently 2 groups are in order, next time it will be 4 groups in order
gap *= 2;
}
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56907 people are learning the system