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

This article introduces the relevant knowledge of "what is the iterative implementation method of merging and sorting". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Iterative implementation of merge sorting

Before formally looking at the code, I hope you know the recursive implementation of merge sorting. It doesn't matter if you are not familiar with it. See this article illustrating the "merge sorting" algorithm (revised version) article.

Iterative and Recursion (Iteration & Recursion) have always cherished each other. The recursive implementation of any algorithm can turn it into an iterative implementation, as long as the cost is small enough and the benefits (space and time efficiency improvement) are high enough.

Merge sorting can also be done, but the iterative implementation of merge sorting is relatively special, unlike most of the transformation between recursion and iteration, merge sorting does not need an explicit stack auxiliary stack in the program, but it can also remove recursive calls and realize merge sorting in an iterative way.

This diagram must be familiar, which is the division and governance in the standard recursive implementation, and when using iterative implementation, there are two changes in strategy:

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

The way of division is circular (iterative) rather than recursive.

The strategy of dividing is different from the way of recursion, and it is still in line with the idea of merging and sorting.

Let's still take the following array as an example (feels like this array is omnipotent, ):

Step 1: merge 5 and 1

Step 2: merge 4 and 2

Step 3: merge 8 and 4

Step 4: merge [1, 5, 2, 4]

Step 5: merge [4pr 8]

Step 6: merge [1, 2, 4, 5, 4, 8]

Seeing here, we can't clearly see the difference between iteration and recursion of merge sorting.

This time it will be clear that the merge order in the iterative implementation of merge sorting is significantly different from that of recursion, which splits the original array of length n into two, and then divides two (1 beat 2) arrays into two until it is divided into n elements of length 1. Then pairwise merge according to size, and so on, until an ordered array containing n numbers is finally formed.

The iteration is different. By default, the elements in the array are treated as n elements of length 1; two elements are merged in turn, and four elements are merged as a group (less than 4, for example, [4d8]. If less than 4, merge according to the remaining number of 2), and finally merge the two elements of nram as a group to get our ordered array.

In the iterative implementation, the score process does not seem to be seen only from the diagram, but in fact, the score has been done before the merge, but this score is different from the recursive call score, but uses iteration.

Ignoring the implementation details of the merge, let's just look at how iterations are implemented.

Static void mergeSort (int arr [], int n) {int curr_size; / / identifies the size of the subarray that is currently merged, from 1 known to 2 int left_start; / / identifying the starting point of the subarray to be merged (curr_size = 1 Curr_size 2, no extra space is used for merge operation at this time. Move the elements before start2 and after start1 (including start1) backward, and copy 2 to the location pointed to by start1, and then move start1, start2, and mid backward:

Step 3: compare the element 4 that start1 points to and the element 4 that start2 points to, 4 = 4, so move start1 directly to the right, that is, start1++.

Step 4: similar to step 2, compare element 5 pointed by start1 with element 4,5 > 4 pointed by start2, move 4 forward, move 5 backward, and then move start1, start2, and mid backward:

Step 5: compare element 5 pointed to by start1 with element 8 pointed to by start2, * * 5

Mid, indicating that the merge is complete.

The implementation code of the merge operation with space complexity:

Static void merge (int arr [], int start1, int mid, int end) {int start2 = mid+1; / / if the element mid is less than or equal to mid+1, the array is ordered and there is no need to merge if (arr [mid])

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.