归并排序

归并排序

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置

3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

代码

---

#include <stdio.h>

int helperArr[10];

void Merge(int arr[], int l, int mid, int r)
{
    int i = l;
    int p1 = l;
    int p2 = mid + 1;
    while (p1 <= mid && p2 <= r) {
        helperArr[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
    }
    while (p1 <= mid) {
        helperArr[i++] = arr[p1++];
    }
    while (p2 <= r) {
        helperArr[i++] = arr[p2++];
    }

    for (; l <= r; l++) {
        arr[l] = helperArr[l];
    }
}

void MergeSort(int arr[], int l, int r)
{
    if (l == r) {
        return;
    }
    int mid = l + ((r - l) >> 1); // =(l+r)/2 因为l+r有可能会溢出，所以改成减法的方式
    MergeSort(arr, l, mid);
    MergeSort(arr, mid + 1, r);
    Merge(arr, l, mid, r);
}

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

int main()
{
    int arr[10] = {6, 0, 5, 3, 15, 21, 13, 9, 12, 8};
    PrintArr(arr, 10);
    MergeSort(arr, 0, 9);
    PrintArr(arr, 10);
    return 0;
}