归并排序 — C++实现

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(n\logn)}（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

#include <iostream>

using namespace std;

void merge(int a[], int begin, int mid, int end);
void merge_sort(int a[], int begin, int end);

int main()
{
    int arr[9] = { 5, 2, 7, 1, 9, 3, 2, 4, 6 };

    for (auto i : arr)
        cout << i << " ";
    cout << endl;

    merge_sort(arr, 0, 8);

    for (auto i : arr)
        cout << i << " ";
    cout << endl;
}

void merge(int a[], int begin, int mid, int end)
{
    int n1 = mid - begin + 1;
    int n2 = end - mid;
    int* L = new int[n1];
    int* R = new int[n2];
    for (int i = 0; i < n1; i++)
        L[i] = a[begin + i];
    for (int j = 0; j < n2; j++)
        R[j] = a[mid + 1 + j ];

    int i = 0, j = 0;
    for (int k = begin; k < end + 1; k++) {
        if (i > n1 - 1) {
            a[k] = R[j];
            j++;
        }else if (j > n2 - 1) {
            a[k] = L[i];
            i++;
        }else if (L[i] <= R[j]) {
            a[k] = L[i];
            i++;
        }else {
            a[k] = R[j];
            j++;
        }
    }
    delete []L;
    delete []R;
}

void merge_sort(int a[], int begin, int end)
{
    if (begin < end) {
        int mid = (end + begin) / 2;
        merge_sort(a, begin, mid);
        merge_sort(a, mid+1, end);
        merge(a, begin, mid, end);
    }
}

注：本实现未使用哨兵项