#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <time.h>
#include <sys/timeb.h>
#define MAX 20
using namespace std;
 
int* create_list(int len) {

    int* list = (int *)malloc(sizeof(int) * len);
    memset(list, 0, sizeof(int) * len);
    for (int i = 0; i < len; i++) {
        list[i] = rand() % 200;
    }
    return list;
}

void print_list(int list[], int len) {

    if (NULL == list || len <= 0) {
        return;
    }
    int line = 0;
    for (int i = 0; i < len; i++, line ++) {
        if (line > 9)
        {
            cout << endl;
            line = 0;
        }
        cout << list[i] << "  ";
    }
    cout << endl;
}

long getSysTime() {

    struct timeb tb;
    ftime(&tb);
    return tb.time * 1000 + tb.millitm;
}

// 合并算法 從小到大
void Merge(int list[], int start, int end, int mid, int* tmp) {

    int i_start = start;
    int i_end = mid;
    int j_start = mid + 1;
    int j_end = end;
    // 表示輔助空間有多少元素
    int length = 0;
    // 合并兩個有序序列
    while (i_start <= i_end && j_start <= j_end) {
        if (list[i_start] < list[j_start]) {
            tmp[length++] = list[i_start++];
        } else {
            tmp[length++] = list[j_start++];
        }
    }
    // i序列
    while (i_start <= i_end) {
        tmp[length++] = list[i_start++];
    }
    // j序列
    while (j_start <= j_end) {
        tmp[length++] = list[j_start++];
    }
    // 輔助空間的數(shù)據(jù)賦值給原空間
    for (int i = 0; i < length; i++) {
        list[start + i] = tmp[i];
    }
}

void MergeSort(int list[], int start, int end, int* tmp) {

    if (start >= end) {
        return;
    }
    // 取中間點
    int mid = (start + end) / 2;
    // 分組
    /// 左半邊
    MergeSort(list, start, mid, tmp);
    /// 右半邊
    MergeSort(list, mid + 1, end, tmp);
    // 合并
    Merge(list, start, end, mid, tmp);
}

int main(int argc, char* argv[]) {

    srand((unsigned int)time(NULL));

    int *list = create_list(MAX);

    // 輔助空間
    int *tmp = (int *)malloc(sizeof(int) * MAX);
    print_list(list, MAX);
    MergeSort(list, 0, MAX - 1, tmp);
    print_list(list, MAX);
    // 釋放
    free(tmp);
    free(list);
    return 0;
}