插入排序和归并排序

#include <iostream>
#include <vector>

using namespace std;


//插入排序
insertionSort(vector<int> &A)
{
    int n = A.size();
    for(int j=1; j < n ; j++)
    {
        int key = A[j];
        //insert A[j] into the sorted sequence A[1, ...j -1];
        int i = j-1;
        while(i >= 0 && A[i] > key)
        {
            A[i+1] = A[i];
            i--;
        }
        A[i+1] = key;
    }
}

//归并排序
Merge(vector<int> &A, int p , int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q;
    vector<int> L(n1+1);
    vector<int> R(n2+1);
    //注意这两个细节
    for(int i=0; i < n1; i++)
    {
        L[i] = A[p+i];
    }
    for(int i=0; i<n2; i++)
    {
        R[i] = A[q+i+1];
    }

    L[n1] = 99999999; // 哨兵
    R[n2] = 99999999;
    int i = 0,j = 0;
    for(int k = p; k <= r; k++)
    {
        if(L[i] <= R[j])
        {
            A[k] = L[i];
            i++;
        }
        else
        {
            A[k] = R[j];
            j++;
        }
    }

}

mergeSort(vector<int> &A, int p ,int r)
{
    //先分在并
    if(p < r)
    {
       int  q = (p+r) / 2;
        mergeSort(A,p,q);
        mergeSort(A,q+1,r);
        Merge(A,p,q,r);
    }

}


int main()
{
    vector<int> A = {1,3,2,7,6,5,8};
    mergeSort(A,0,6);
    for(int i = 0; i < A.size(); i++)
    {
        cout << A[i] << " ";
    }
    return 0;

}