In the last article, we familiarized ourselves with relic sorting of mergers (causing primarily historical interest). And what is the trend today?



Balanced merge algorithms are commonly used to familiarize themselves with the concept of merge ordering. The term “balance” means that the algorithm recursively splits an array and its subarrays into approximately equal parts. Today we look at how it looks in practice.



A pair of functions is the same for both methods. And in general, that “up and down”, that “up and down” is practically the same algorithm, just shown from different angles.

')

We will, in fact, need to merge the two halves of the segment into one subarray. The halves are simultaneously sorted in one array, the current elements in both enumerations are compared and the smaller element goes to the second array:

//   A[iBegin: iMiddle - 1] //   A[iMiddle: iEnd - 1] //:   B[iBegin: iEnd - 1] void Merge(A[], iBegin, iMiddle, iEnd, B[]) { i = iBegin, j = iMiddle; //       ... for (k = iBegin; k < iEnd; k++) { //     //  <=    if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) { B[k] = A[i]; i++; } else { B[k] = A[j]; j++; } } } 

Copy a segment from one array to another. Both implementations operate on two arrays, the data must be constantly driven from the main to the auxiliary and back:

 //    A[] //   B[] void CopyArray(A[], iBegin, iEnd, B[]) { for(k = iBegin; k < iEnd; k++) B[k] = A[k]; } 

Downward balanced merger

First, the entire array is taken, after which the recursive descent begins. The array is dictated until we reach the subarrays of one element (which are sorted by themselves). Then, the recursion starts the reverse lift, merging the subarrays along the way (the size of which at each level doubles).

 //  A[]     // B[]   void TopDownMergeSort(A[], B[], n) { CopyArray(A, 0, n, B); // A[]  B[] TopDownSplitMerge(B, 0, n, A);// B[]    A[] } //    A[],  B[]    // : iBegin ; iEnd   void TopDownSplitMerge(B[], iBegin, iEnd, A[]) { // size == 1,     if(iEnd - iBegin < 2) return; // size > 1,     iMiddle = (iEnd + iBegin) / 2;//iMiddle -   //     A[]  B[] TopDownSplitMerge(A, iBegin, iMiddle, B);//   TopDownSplitMerge(A, iMiddle, iEnd, B);//   //    B[]  A[] Merge(B, iBegin, iMiddle, iEnd, A); } 

Upward balanced merger

This is an iteration through the array, along the way we first take the adjacent minimal arrays (from one element) and pair them together. Receiving double sorted subarrays at each step, we again merge the neighbors, and so continue until we get the entire array at the output, already in sorted form.

 //  A[]     // B[]   void BottomUpMergeSort(A[], B[], n) { //      A[]  «». //    : //× 2, 4, 8, 16, ... -   ,       for (width = 1; width < n; width = 2 * width) { //     width for (i = 0; i < n; i = i + 2 * width) { //   : //A [i: i + width - 1]  A [i + width: i + 2 * width - 1]  B[] //  A[i: n - 1]  B[] ( i + width > = n) Merge(A, i, min(i + width, n), min(i + 2 * width, n), B); } //   B[]    2 * width //  B[]   A[]    //     A[]  B[] CopyArray(B, 0, n, A); // B[]  A[] //      2 * width } } 

In general, a descending implementation is preferable, since it more effectively uses two arrays that are simply constantly changing the "main / auxiliary" roles. In the ascending version, array A is always main, and array B is always auxiliary. As a result, after each iteration, the data from B must be returned in full to A, which does not contribute to the improvement of algorithmic complexity. On the other hand, the implementation of the ascending is simpler, it does not even have a recursion.

Unbalanced merger

From the very word "balance" breathes some kind of reliability, stability. It may even give the impression that a good algorithm must necessarily be balanced. And “imbalance” is associated with some kind of shakiness and distortions. Well, really, shouldn't a balanced one be better in all respects than an unbalanced one ?



In fact, it happens worse. Of course, the division of subarrays into equal halves (which is implied by the balance for merge sorts) is much easier to implement. Divide the array in half and apply recursion to each half. Actually, in this lightness lies the main advantage of a balanced merger to an unbalanced one.



In the following publications we will look at unbalanced ways. They are noticeably more difficult to understand and implement. The data for the subsequent merge will be distributed among auxiliary arrays not evenly and evenly, but in accordance with a number of generalized Fibonacci numbers. And this will allow to achieve powerful results that are unattainable for simplified balanced methods.

Links

Merge ( Google-translate ), Merge

Articles series:

• Excel application AlgoLab.xlsm
• Exchange sorting
• Sorting inserts
• Sort by selection
• Merge sort
  
  
  • Balanced merger top-down and bottom-up
  • Multiphase merge sorting
  • Cascade Merge Sort
  • Oscillating merge sort
  • Filamentous and immiscible sorting
  • Merge sort comparison

The next sorted sorts are now available in the AlgoLab application (anyone who studies the algorithms using this Excel application, update the file).



Temporarily there is a restriction on the arrays - their size should be a power of two (due to some of the difficulties encountered when programming the visualization). A little later, it will be possible to sort any arrays.

The article was written with the support of the EDISON Software company, which, using cloud services, creates embedded software and develops mobile applications on JAVA .