#include <iostream>

using namespace std;

/*

 * 나누어져 정렬된 두 리스트를 병합

 *

 * initList: 병합될 리스트

 * mergedList : 병합, 정렬된 리스트

 * l: initList에서의 시작 위치(병합될 첫 리스트의 시작점)

 * m: initList에서의 중간 위치(나누어진 위치, 병합될 첫 리스트의 끝점, 여기서 1을 더하면 병합될 두번째 리스트의 시작)

 * n: initList에서의 끝 위치(병합될 두번째 리스트의 끝점)

 */

void printArray(int A[], int size);

void merge(int* initList, int* mergedList, const int l, const int m, const int n) {

    /*

     * i1: 첫번째 리스트 index

     * i2: 두번째 리스트 index

     * iResult: 병합, 정렬된 리스트의 index

     */

    int i1 = 0;

    int iResult = 0;

    int i2 = 0;

    for (i1 = l, iResult = l, i2 = m + 1; i1 <= m && i2 <= n; iResult++) {

        if (initList[i1] <= initList[i2]) {

            mergedList[iResult] = initList[i1];

            i1++;

        }

        else {

            mergedList[iResult] = initList[i2];

            i2++;

        }

    }

    /*

     * 첫번째 리스트 혹은 두번째 리스트의 나머지를 결과에 추가

     */

    if (i1 > m)

        for (int t = i2; t <= n; t++)

            mergedList[iResult + t - i2] = initList[t];

    else

        for (int t = i1; t <= m; t++)

            mergedList[iResult + t - i1] = initList[t];

}

/*

 * initList: 정렬할 리스트

 * resultList: 정렬한 리스트

 * n: 리스트의 전체 크기

 * l: 리스트내의 하위 리스트의 크기(Merge될 리스트의 크기)

 */

void MergePass(int* initList, int* resultList, const int n, const int l) {

    int i = 0;

    /*

     * l = 1  merge(0, 0, 1)   merge(2, 2, 3)   .........   merge(6, 6, 7)

     * l = 2  merge(0, 1, 3)   merge(4, 5, 7)

     * l = 4  merge(0, 3, 7)

     * 이처럼 l이 증가함에 따라 정렬할 하위 리스트들도 같은 크기로 증가한다

     */

    for (; i < n - 2 * l + 1; i += 2 * l) {

        merge(initList, resultList, i, i + l - 1, i + 2 * l - 1);

    }

    /*

     * 그러나 만약 원 리스트의 크기가 1, 2, 4, 8 처럼 짝수가 아닌 홀수일 경우 

     * n = 9

     * merge(0, 0, 1)   merge(2, 2, 3)  ......  merge(6, 6, 7)  merge(8, 8, ?)  이처럼 out of index 오류가 발생할 것이다.

     * 따라서 이런 오류를 막기 위해 아래 조건문이 필요하다.

     */

    if ((i + l - 1) < n - 1)

        merge(initList, resultList, i, i + l - 1, n - 1);

    else

        for (int t = i; t < n; t++)

            resultList[t] = initList[t];

}

/*

 * Merge Sort

 * MergePass에 리스트를 1개, 2개, 4개의 원소로 나누어 Merge할 수 있도록

 * 원 리스트를 임시 리스트에 Merge하고,

 * 다시 Merge 정렬되어 2배 크기가 된 리스트의 리스트인

 * 임시 리스트를 다시 원 리스트에 Merge.

 * list: 정렬할 리스트

 * n: 정렬할 리스트의 길이

 */

void MergeSort(int* list, const int n) {

    int* tempList = new int[n];

    for (int l = 1; l < n; l *= 2) {

        /*

         * 원 list를 임시 list에 merge 

         */

        MergePass(list, tempList, n, l);

        l *= 2;

        /*

         * 임시 list를 원 list에 merge

         */

        MergePass(tempList, list, n, l);

    }

    delete[]tempList;

}

/*

 * UTILITY FUNCTIONS

 * Function to print an array

 */

void printArray(int A[], int size)

{

    int i;

    for (i = 0; i < size; i++)

        printf("%d ", A[i]);

    printf("\n");

}

int main() {

    int list[] = { 11, 17, 13, 10, 6, 1, 8, 3 };

    int listLen = sizeof(list) / sizeof(list[0]);

    cout << "origin : ";

    printArray(list, listLen);

    cout << endl;

    MergeSort(list, listLen);

    cout << "result : ";

    printArray(list, listLen);

    cout << endl;

}