Merge sort of C language implementation

Its basic pattern is as follows:

Decomposition: the decomposition of a problem into subproblems similar to the original problem

Solution: recursive solution to each subproblem

Merge: merge the results of the subproblem to obtain the solution of the original problem.

Now let's use the recursive algorithm, using the above divide-and-conquer idea to solve the merge sort.

                                          Merge sort (non-descending)

Decomposition: decomposes merge sort into two subproblems

Pseudo code:

MERGE_SORT(A, begin, end)
if begin < end
   then mid<- int((begin + end)/2)
           MERGE_SORT(A, begin, mid)
           MERGE_SORT(A, mid+1, end)
           MERGE(A, begin, mid, end)

Solution: recursively solves each subproblem, and each subproblem continues to recursively call itself until "begin< When the condition "end" is not satisfied, that is, "begin==end", there is only one element, which is clearly in order, and then the next merge.

Merge: there is an implicit problem with the results of the merged subproblems that the subproblems are already sorted (starting with the merge of two nitrogen sequences). This is done by comparing the first element of the two subsequences with the smaller written final result, and then comparing it further, as shown in the following figure:

< img border = 0 id = theimg onclick = window. The open (enclosing SRC) src=//files.jb51.net/file_images/article/201302/201322192038118.png >

              Figure: the sorted array is 2, 4, 6& PI; 1 3 5

              Store 2, 4, 6, and 1, 3, and 5 in an array. Compare the first element of the two arrays with the smaller one in the larger array, until both elements are 32767.

              There's an infinite 32,767 flavors here, because in c   Int is 32 bits, which means the range is -32768-- -32768. Using infinity as a target can reduce the judgment of whether two small arrays are empty or not. With the target, directly determining the number of elements in a large array is finished.  

        The execution process in the whole process is shown in the following figure:

< img border = 0 id = theimg onclick = window. The open (enclosing SRC) src=//files.jb51.net/file_images/article/201302/201322192213943.png >

Decompose + execute from the top down and merge from the bottom up.

  The code is attached:

#include <stdio.h>
void MERGE(int *A, int b, int m, int e)
{       
        int l = m-b+1, r = e-m, i;
        int L[l+1], R[r+1];
        for(i=0; i< l; i++)
        {
            L[i] = A[b+i];
        }
        for (i=0; i< r; i++)
        {
            R[i] = A[m+i+1];
        }
        L[l] = 32767;
        R[r] = 32767;
        l = 0;
        r = 0;
        for(i=0; i< e-b+1; i++)
        {
            if(L[l] < R[r])
            {
                A[b+i] = L[l];
                l ++;
            }
            else            {
                A[b+i] = R[r];
                r ++;
            }
        }
}
 
void MERGE_SORT(int *A, int b, int e)
{
        if(b < e)
        {
            int m = (b + e) / 2;
            MERGE_SORT(A, b, m);
            MERGE_SORT(A, m+1, e);
            MERGE(A, b, m, e);
        }
}
int main()
{
        int A[500];
        int lens, i;
        printf("Please Enter the lenghth of array:");
        scanf("%d", &lens);
 
        printf("Please Enter the elements of the array:");
        for(i=0; i< lens; i++)
            scanf("%d", &A[i]);
 
        MERGE_SORT(A, 0, lens-1);
 
        printf("the result of the sort is:n");
        for(i=0; i< lens; i++)
        {
            printf("%d ", A[i]);
        }
        return 0;
}