归并排序

归并排序的基本思路：

• merge函数将两个有序数列归并到一个有序数列中
• 根据分治法，利用递归，不断归并有序数列
• 递归最终的单元操作为：将两个分别只含有一个元素的有序数列归并为一个数列

#include <iostream>
using namespace std;

void merge(int *input, int start, int mid, int end, int *temp) {
    int k = 0;
    int leftNum = mid;
    int rightNum = end;
    int i = start;
    int j = mid + 1;
    
    while (i <= leftNum && j <= rightNum) {
        if (input[i] < input[j]) {
            temp[k++] = input[i++];
        } else {
            temp[k++] = input[j++];
        }
    }
    while (i <= leftNum) {
        temp[k++] = input[i++];
    }
    while (j <= rightNum) {
        temp[k++] = input[j++];
    }
    for (i = 0; i < k; i++) {
        input[start + i] = temp[i];
    }
}


void mergeSort(int *input, int start, int end, int *temp) {
    if (start < end) {
        int mid = (start + end) / 2.;
        mergeSort(input, start, mid, temp);
        mergeSort(input, mid + 1, end, temp);
        merge(input, start, mid, end, temp);
    }
}
int main() {
    int a[] = {3,5,6,2,1,9,8};
    int p[7];
    mergeSort(a, 0, 6, p);
    
    for (int i = 0; i < 7; i++) {
        cout<<a[i];
    }
    cout<<endl;
    return 0;
}