#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;

int* generateRandomArray(int n, int rangL, int rangR)
{
    srand(time(NULL));
    int* arr = new int[n];
    for (size_t i = 0; i < n; i++)
        arr[i] = rand() % (rangR - rangL + 1) + rangL;
    return arr;
}

void print_arr(int* arr, int n)
{
    for (size_t i = 0; i < n; i++)
        std::cout << arr[i] << ' ';
    std::cout << "\n";
}


// arr[l......r]
void merge(int* arr, int l, int r)
{
    if (l < r)
    {
        int mid = l + (r-l)/2;
        merge(arr, l, mid);         //arr[l......mid]
        merge(arr, mid + 1, r);     //arr[mid+1....r]
        int *tmp = new int[r-l+1];
        for (size_t i = l, j = mid + 1, k=0; k < r-l+1; k++)
        {
            if(i > mid)
                tmp[k] = arr[j++];
            else if (j > r)
                tmp[k] = arr[i++];
            else if(arr[i] > arr[j])
                tmp[k] = arr[j++];
            else
                tmp[k] = arr[i++];
        }
        for (size_t i = l; i <= r; i++)
            arr[i] = tmp[i-l];
        print_arr(tmp, r-l+1);
        delete[] tmp;
    }
}



void insert(int *arr, int n)
{
    for (size_t i = 1; i < n; i++)
    {
        int tmp = arr[i], j=i;
        while (j>0 && tmp < arr[j-1])
        {
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = tmp;
    }
}


/*
arr 表示待调整的数组
k 表示待调整元素的索引
n 表示数组中元素的个数 
 */
void shift_down(int* arr, int k, int n)
{
    while (k <= n/2-1)
    {
        int kk = 2*k + 1;
        if(kk + 1 < n && arr[kk + 1] > arr[kk])
            kk = kk + 1;
        if(arr[kk] <= arr[k])
            return;

        swap(arr[kk], arr[k]);
        k = kk;
    }
}

void heap_sort(int* arr, int n)
{
    for (int i = n/2-1; i >= 0; i--)
        shift_down(arr, i, n);
        
    for (size_t i = 0; i < n; i++)
    {
        swap(arr[0], arr[n-i-1]);
        shift_down(arr, 0, n-i-1);
    }
}

int main()
{
    int n = 25;
    int* arr = generateRandomArray(n, 0, 100);
    print_arr(arr, n);
    //insert(arr, n);
    merge(arr, 0, n-1);
    //shift_down(arr, 1, 10);
    print_arr(arr, n);
    system("pause");
    return 0;
}