統合ソート(C言語実装)

その基本パターンは以下の通りです。
一つの問題をもとの問題と似たような問題に分解します。
解決：再帰的に各サブ問題を解決する
合併：合併子問題の結果、元の問題の解が得られました。
現在は再帰的アルゴリズムを用いて、上の分治思想を用いて合併秩序を解いています。
                      並べ替えを結合(降順ではない)
合併を二つの問題に分類する。
疑似コード:

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)

解決：再帰的に各サブ問題を解いて、各サブ問題はまた再帰的に自分を呼び起こし続け、「begin＜end”という条件が満たされない時、すなわち「begin==end」という条件が満たされない時に、この時には一つの要素しかなくて、明らかに秩序が整然としています。
合併：合併のサブ問題の結果には、各サブ問題が順序付けされている問題（2つの窒素要素シーケンスからマージが開始されている）が暗黙的に存在しています。作り方は、2つのサブシーケンスの最初の要素を比較して最終結果を記入し、下の図のように比較します。

        図中：並べ替え待ち行列は2 4 6です。  1 3 5
        2 4 6と3 5をそれぞれ1つの配列に保存し、2つの配列の最初の要素サイズを比較すると、2つの配列の要素が32767であるまで大きな配列に保存されます。
        ここは32767味が無限大です。c言語の中ですから。  intタイプは32ビットで、範囲は-32768----322768です。無限大をターゲットとすると、二つの小さい配列が空いているかどうかを判断できます。標的があったら、直接的に大きい配列要素が何回で並べられたかを判断します。 
     全体の過程で実行する過程は下図のように示されています。

分解+実行時は上から下へ、結合時は下から上へと進みます。
 コードの送信:

#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:
");
        for(i=0; i< lens; i++)
        {
            printf("%d ", A[i]);
        }
        return 0;
}