Detailed explanation of merge sorting algorithm in Java

Detailed explanation of merge sorting algorithm in Java

Merge sorting algorithm, as its name suggests, is an algorithm that divides and then combines. Its algorithm idea is to decompose the array to be sorted into a single element. Each element is a single individual, and then sort the adjacent two elements in order from small to large or from large to small to form a whole. Each whole contains one or two elements, Then continue to "merge" the adjacent whole. Because each whole is sorted, you can merge it with a certain algorithm. After merging, each whole contains three to four elements. Continue to merge the adjacent whole until all the whole are merged into a whole. The final whole is the result of sorting the original array.

For adjacent whole, The idea of merging is to take the smallest element of the two whole (assuming that it is actually sorted in ascending order) and put it into a new array and cycle in turn. Finally, the elements in the two whole are taken to get an ascending whole. The merging process is like a pile a and B with two ascending orders (as shown in the figure), take out one element from the top at a time and put it into pile C:

It can be seen from the figure that the elements in two adjacent whole a and B are sorted in ascending order. Now there is a temporary array C. then compare the two elements at the top of a and B, take out the smaller element and put it into C. for the whole of the taken out element, its subscript pointing to the element moves down one bit, Continue to take out the smaller one of the top elements of the two whole and put it into C, and cycle in turn. When a whole element is taken, directly move the elements of the other whole into C. For the whole of C, it is obtained by sorting a and B. because a and B are two adjacent whole, finally, you only need to copy the elements in C to a common whole composed of a and B, so as to achieve the purpose of sorting while merging a and B.

The following is the specific algorithm for merging and sorting:

There are two main methods in the code

The first method is a recursive method. For recursive methods, we must clearly define the function of the method. The purpose of this recursive method is to sort the elements from start to end of the incoming array, and TMP is an auxiliary array. In the specific implementation of this method, we can see that the idea is to continue to call recursion to sort the elements from start to mid, and then call recursion to sort the elements from mid to end. After these two methods, the elements from start to mid and from mid to end are sorted. At this time, we need to call the second method.

The function of the second method is to merge two sorted parts. For the first method, the second method is executed in the last step, that is, the function of the method is completed after merging the sorted parts in the previous two steps. For the second method, the implementation idea is the same as that described above. Take a smaller element from the top of two stacks of cards and put it into the temporary array. When a stack of cards is taken, put the remaining array elements into the second stack of cards, and finally put the elements of the temporary array back into the original array.

This paper mainly explains the idea of merging and sorting in detail, and analyzes the code combined with the specific code and thought.

If you have any questions, please leave a message or go to the community of this site for exchange and discussion. Thank you for reading. I hope it can help you. Thank you for your support to this site!