#include <iostream>
using namespace std;

//直接插入排序，时间复杂度O(n*n)，空间复杂度O(1)
void insert_sort(int a[], int n)
{
    for(int i = 1; i < n; i++)
    {
        int temp = a[i];
        int j = i-1;
        for(; a[j]> temp; j--)
            a[j+1] = a[j];
        a[j+1] = temp;
    }
}

//冒泡排序， 时间复杂度O(n*n)，空间复杂度O(1)
void bubble_sort(int a[], int n)
{
    for(int i = 0; i < n; i++)
    {
        bool flag = true;
        for(int j = n-1; j > i; j--)
        {
            if(a[j] < a[j-1])
            {
                swap(a[j], a[j-1]);
                flag = false;
            }
        }
        if(flag) break;
        /*快速冒泡的操作，如果某一轮没有发生交换，
        则已经有序，直接跳出 */
    }
}

//选择排序，时间复杂度O(n*n)，空间复杂度O(1)
void select_sort(int a[], int n)
{
    for(int i = 0; i < n; i++)
    {
        int min = i;
        for(int j = i; j < n; j++)
            if(a[j] < a[min]) min = j;
        swap(a[i], a[min]);
    }
}

//快速排序的划分操作
int partition(int a[], int low, int high)
{
    int pivot = a[low];
    while(low < high)
    {
        while(low < high && a[high] >= pivot)
            high--;
        a[low] = a[high];
        while(low < high && a[low] <= pivot)
            low++;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}

/*快速排序，时间复杂度平均O(n*logn)，最坏O(n*n)
空间复杂度O(1),运用递归的方法，需调用划分函数*/
void quick_sort(int a[], int low, int high)
{
    if(low >= high) return;
    int pivotpos = partition(a, low, high);
    quick_sort(a, low, pivotpos-1);
    quick_sort(a, pivotpos+1, high);
}

//归并排序的归并操作
void merge(int a[], int low, int mid, int high, int b[])
{
    for(int i = low; i <= high; i++) b[i] = a[i];
    int i = low, j = mid+1;
    int index = low;
    for(; i <= mid && j <= high; index++)
    {
        if(b[i] <= b[j]) a[index] = b[i++];
        else a[index] = b[j++];
    }
    while(i <= mid) a[index++] = b[i++];
    while(j <= high) a[index++] = b[j++];
}

//归并排序，使用递归，时间复杂度O(n*logn)，空间复杂度O(n)
void merge_sort(int a[], int low, int high, int b[])
{
    if(low >= high) return;
    int mid = (low + high)/2;
    merge_sort(a, low, mid, b);
    merge_sort(a, mid+1, high, b);
    merge(a, low, mid, high, b);
}

//输出函数
void print_sort(int a[], int n)
{
    for(int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
}

int main()
{
    int n = 10000;
    int number[n+1];
    for(int i = 0; i < n; i++)
        number[i] = rand() % 100000;
    cout << "start" << endl;
//  print_sort(number, n);
    int b[n];
    merge_sort(number, 0, n-1, b);
    print_sort(number, n);
    return 0;
}