/* file name: mergeSort.c*/
/* 合併排序 */

#include <stdio.h>
#include <stdlib.h>
void selectionSort(int[], int);
void mergeSort(int[], int[], int[], int, int);
void flushBuffer(void);
void printDashLine(void);

int main()
{
    int data1[10], data2[10], data3[20];
    int size1 = 0, size2 = 0, i;

    printf("\n請輸入data1陣列的資料(輸入 0 表示結束): ");
    /* 要求輸入數字直到輸入數字為 0 */
    do {
        scanf("%d", &data1[size1]);
    }  while(data1[size1++] != 0);
    flushBuffer();
    printf("未排序的資料 : ");
    for (i = 0; i < size1-1; i++)
        printf("%d  ", data1[i]);
    printf("\n");
    
    printf("\n請輸入data2陣列的資料(輸入 0 表示結束): ");
    /* 要求輸入數字直到輸入數字為 0 */
    do {
        scanf("%d", &data2[size2]);
    }  while(data2[size2++] != 0);
    flushBuffer();
    printf("未排序的資料 : ");
    for (i = 0; i < size2-1; i++)
        printf("%d  ", data2[i]);
    printf("\n");

    /* 先使用選擇排序將兩數列排序，再作合併 */
    selectionSort(data1, --size1);
    selectionSort(data2, --size2);
    
    printDashLine();
    /* 印出這兩個陣列，分別排序後的資料 */
    printf("利用選擇排序後的資料如下: \n");
    printf("Data1 : ");
    for(i = 0; i < size1; i++)
        printf("%d  ", data1[i]);
    printf("\n");
    
    printf("Data2 : ");
    for(i = 0; i < size2; i++)
        printf("%d  ", data2[i]);
    printf("\n");
    printDashLine();
    
    mergeSort(data1, data2, data3, size1, size2);
    printDashLine();
    
    printf("由小至大排序後的資料: ");
    for (i = 0; i < size1+size2; i++)
        printf("%d  ", data3[i]);
    printf("\n");

    return 0;
}

void selectionSort(int data[], int size)
{
    int base, compare, min, temp;
    for (base = 0; base < size-1; base++) {
        min = base;
        for (compare = base+1; compare < size; compare++)
            if (data[compare] < data[min])
                min = compare;
        temp = data[min];
        data[min] = data[base];
        data[base] = temp;
    }
}

void mergeSort(int data1[], int data2[], int data3[], int size1, int size2)
{
    int arg1, arg2, arg3, i;
    data1[size1] = 32767;
    data2[size2] = 32767;
    arg1 = 0;
    arg2 = 0;
    for (arg3 = 0; arg3 < size1+size2; arg3++) {
        /* 比較兩數列，資料小的先存於合併後的數列 */
        if (data1[arg1] < data2[arg2]) {
            data3[arg3] = data1[arg1];
            arg1++;
        }
        else {
            data3[arg3] = data2[arg2];
            arg2++;
        }
        printf("#%2d Step: ", arg3+1);
        for (i = 0; i < arg3+1; i++)
            printf("%d  ", data3[i]);
        printf("\n");
    }
}

void flushBuffer()
{
    while (getchar() != '\n')
        continue;
}

void printDashLine()
{
    for(int i = 0; i < 48; i++)
        printf("-");
    printf("\n");
}