Merge sort of Java sorting algorithm summary

This paper describes the merge sort of Java sorting algorithm. Share with you for your reference. The specific analysis is as follows:

Merge, also known as merge algorithm, refers to the operation of merging two sorted sequences into one sequence. Similar to quick sort, let's look at the implementation of merge in Java.

Merge is to merge two (or more) ordered tables into a new ordered table, that is, divide the sequence to be sorted into several subsequences, each subsequence is ordered, and then merge the ordered subsequences into an overall ordered sequence.

Merge sort is an effective sort algorithm based on merge operation. The algorithm is a very typical application of divide and conquer. The ordered subsequences are combined to obtain a completely ordered sequence; that is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are combined into one ordered table, it is called 2-way merging.

The merge sort algorithm is stable. The array needs o (n) additional space, and the linked list needs o (log (n)) additional space. The time complexity is O (NLog (n)). The algorithm is not adaptive and does not need random reading of data.

working principle:

1. Apply for a space so that its size is the sum of two sorted sequences. The space is used to store the merged sequence. 2. Set two pointers. The initial positions are the starting positions of the two sorted sequences. 3. Compare the elements pointed to by the two pointers, select a relatively small element into the merged space, and move the pointer to the next position. 4 Repeat step 3 until a pointer reaches the end of the sequence. 5. Copy all the remaining elements of the other sequence directly to the end of the merged sequence

Code implementation:

Merge sort is a relatively stable sort That is, the order of equal elements will not change For example, when inputting record 1 (1) 3 (2) 2 (3) 2 (4) 5 (5) (the keyword of the record is in parentheses), 2 and 2 in output 1 (1) 2 (3) 2 (4) 3 (2) 5 (5) are in the order of input This is very important when the data to be sorted contains multiple information and should be sorted according to one of them, and other information should be sorted according to the input order as much as possible This is also its advantage over quick sort

I hope this article will be helpful to your Java programming.