多路归并排序算法(归并排序算法过程图解)

归并排序是在归并操作上实现的。先了解一下归并操作的原理。

归并操作：将两个有序数组合并为一个新的有序数组。

如有序数组A=[1, 4, 6], B=[2, 4, 5]，将其进行合并。设置变量下标i和j分别表示数组A和B的下标。遍历完数组A和B，最终合并后数组为C。

若A[i] <= B[j]，则将A[i]保存到数组C，并将i++；若A[i] > B[j]，则将B[j]保存到数组C，并将j++；

归并操作的具体实现如下：

void Merge(int *piArrayA, int iArrayALen, int *piArrayB, int iArrayBLen, int *piArrayC)
{
    int iIndex1 = 0;        
    int iIndex2 = 0;        
    int iIndex3 = 0;        

    while ((iIndex1 < iArrayALen) || (iIndex2 < iArrayBLen))
    {
        if ((iIndex1 < iArrayALen) 
        && ((iIndex2 >= iArrayBLen) || (piArrayA[iIndex1] < piArrayB[iIndex2]))
        {
            
            piArrayC[iIndex3++] = piArrayA[iIndex1];
            
            iIndex1++;
        }
        else
        {
            
            piArrayC[iIndex3++] = piArrayB[iIndex2];
            
            iIndex2++;
        }
    }

    return;
}

归并排序是在归并操作基础上实现的。由于归并操作的前提是数组有序，因此我们可以考虑将待排序数组一分为二，先将一分为二的两个子数组变得有序后，再利用归并操作合并该两个子数组，此时整个数组将变得整体有序。

基于上述思想，我们使用递归操作，持续将数组一分为二，将数组划分得只有一个元素时，其将变得天然有序，此时将其合并，层层操作，最终将实现整个数组排序。

具体代码如下：

void Merge(int *piArrayA, int iArrayALen, int *piArrayB, int iArrayBLen, int *piArrayC)
{
    int iIndex1 = 0;        
    int iIndex2 = 0;        
    int iIndex3 = 0;        

    while ((iIndex1 < iArrayALen) || (iIndex2 < iArrayBLen))
    {
        if ((iIndex1 < iArrayALen) 
        && ((iIndex2 >= iArrayBLen) || (piArrayA[iIndex1] < piArrayB[iIndex2]))
        {
            
            piArrayC[iIndex3++] = piArrayA[iIndex1];
            
            iIndex1++;
        }
        else
        {
            
            piArrayC[iIndex3++] = piArrayB[iIndex2];
            
            iIndex2++;
        }
    }

    return;
}



void MergeSort(int *piNums, int iNumsSize)
{
    int iMiddle = 0;
    int aiLeftArray[iNumsSize];
    int aiRightArray[iNumsSize];

    if (iNumsSize <= 1)
    {
        
        return;
    }

    iMiddle = iNumsSize / 2;
    
    
    
    memset(aiLeftArray, 0, sizeof(aiLeftArray));
    memcpy(aiLeftArray, piNums, sizeof(int) * iMiddle);
    MergeSort(aiLeftArray, iMiddle); 

     
    memset(aiRightArray, 0, sizeof(aiRightArray));
    memcpy(aiRightArray, piNums + iMiddle, sizeof(int) * (iNumsSize - iMiddle));
    MergeSort(aiRightArray, iNumsSize - iMiddle);   

    memset(piNums, 0, sizeof(int) * iNumsSize);
    
    Merge(aiLeftArray, iMiddle, aiRightArray, iNumsSize - iMiddle, piNums);

    return;
}

从上可以看出，归并排序利用的是分治思想。