Shulou(Shulou.com)06/01 Report--

The main content of this article is to explain "how to achieve java merge sorting". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn "how to achieve java merge sorting"!

Compared with bubbling, insertion and selection, merge sorting is suitable for large-scale data sorting with time complexity O (N2), and its time complexity is all O (nlogn).

It uses the idea of divide-and-conquer, decomposing big problems into small problems, which are then divided and treated.

First, let's talk about the idea of merging and sorting: divide the array to be sorted from the middle into two, divided into left and right, then sort left and right respectively, and then merge them together (if the left and right sides can continue to be divided into two. (recursive thought) so it's all right! Doesn't it feel pretty simple?

Take a look at the picture.

Get the code! We use recursion to achieve merge sorting.

The key point of the code is that the recursion of recursion is to split the array in two and sort it!

The idea of the merge method is to apply for an empty array with the same length of the left array as the right array to store the results, and then make two cursors I and j point to the left array and the right array, respectively, compare left [I] and Rightj], which is small is put into the result, and then the corresponding cursor + 1. At the end of the loop, the rest of the data that is not stuffed into the result is stuffed into the result. So it's done!

The time complexity of merge sorting is O (nlogn), and it can be seen from the code that result is inserted when left [I] is less than or equal to right [j], so it is a stable sort!

For example, [3, 2, 2, 2, 3]. When divided into left and right and then sorted internally, there is left [2p3], right [2p3]. At this time, the direct order of the two 2s has not been broken, and then the merger is still the second of left plugged into the result first, so it is stable!

But the bad thing about merging is that it is not sorted in place, and you can see that it needs extra array space to store the sorted results. Its space complexity is O (n).

At this point, I believe that you have a deeper understanding of "how to achieve java merger sorting". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.