排序-归并

归并排序

#include <stdio.h>
#include <stdlib.h>

void mySort(int *arr, int nLow, int nHigh)
{
    if (arr == NULL || nLow > nHigh)
        return;
    int Begin1 = nLow;
    int End1 = (nHigh - nLow) / 2 + nLow;
    int Begin2 = End1 + 1;
    int End2 = nHigh;
    int *pTemp = (int *)malloc((nHigh - nLow + 1) * sizeof(int));
    int i = 0;
    while (Begin1 <= End1 && Begin2 <= End2)
    {

        if (arr[Begin1] <= arr[Begin2])
        {
            pTemp[i] = arr[Begin1];
            Begin1++;
        }else
        {
            pTemp[i] = arr[Begin2];
            Begin2++;
        }
        i++;
    }
    while (Begin1 <= End1)
    {
        pTemp[i] = arr[Begin1];
        Begin1++;
        i++;
    }
    while (Begin2 <= End2)
    {
        pTemp[i] = arr[Begin2];
        Begin2++;
        i++;
    }

    for (int i = 0; i < nHigh - nLow + 1; i++)
    {
        arr[nLow + i] = pTemp[i];
    }

    free(pTemp);
    pTemp = NULL;
}

void MergeSort(int *arr, int nLow, int nHigh)
{
    if (arr == NULL || nLow >= nHigh)
        return;

    int mid = (nHigh - nLow) / 2 + nLow;

    MergeSort(arr, nLow, mid);
    MergeSort(arr, mid + 1, nHigh);
    mySort(arr, nLow, nHigh);
}

int main()
{

    int arr[] = {22, 1, 24, 16, 76, 43, 98, 11};
    int nLength = sizeof(arr) / sizeof(int);

    MergeSort(arr, 0, nLength - 1);

    for (int i = 0; i < nLength; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}