/*
基本算法思想：
   首先通過遞歸調用，將原數組不斷的分小，最終將數組分成N份。
   然后將有序的兩組合并成一個有序數組，每合并一次數組的規模
   就會翻倍，最終會將原來無序的數組變成一個有序的數組。
*/
#include<iostream>
using namespace std;
int n = 0;
void mergesort(int p[20], int start, int end);
void smerge(int p[20], int start, int mid, int end);
void main()
{
	int sorts[20];
	int m;
	cout << "請輸入要排序的元素數目：" ;
	cin >> m;
	cout << "請輸入排序的" << m << "元素序列：" << endl;
	for(int i=0; i<m; i++)
		cin >> sorts[i];
	mergesort(sorts, 0, m-1);
	for(i=0; i<m; i++)
		cout << sorts[i] << " ";
	cout << endl;
	cout << "s算法執行的賦值次數：";
	cout << n << endl;
}
/*

 p[20] 要排序元素所在的數組
 start 要排序元素第一個元素的位置
 end   要排序元素最后一個元素的位置
*/
void mergesort(int p[20], int start, int end)
{
	int mid;
	if(start < end)
	{
		mid = (start+end)/2;
		mergesort(p, start, mid);//排序 遞歸調用
		mergesort(p, mid+1, end);//排序 遞歸調用
		smerge(p, start, mid, end);//合并
	}
}
//合并函數
void smerge(int p[20], int start, int mid, int end)
{
	int b[20];
	int i = 0;
	int index1 = start;
	int index2 = mid + 1;
	while(index1<mid+1&&index2<end+1)//兩數組都沒有用光
	{
		if(p[index1] < p[index2])
		{
			n++;
			b[i] = p[index1];
			i++;
			index1++;
		}
		else
		{
			n++;
			b[i] = p[index2];
			i++;
			index2++;
		}
	}
	if(index1 < mid+1)//第二個序列已經用完，而第一個沒有用完
	{
		while(index1 < mid+1)
		{
			b[i] = p[index1];
			i++;
			index1++;
			n++;
		}
	}
	else
	{
		while(index2 < end+1)//第一個序列已經用完，而第二個沒有用完
		{
			b[i] = p[index2];
			i++;
			index2++;
			n++;
		}
	}
	i = 0;
	for(int k=start; k<end+1; k++)//將有序的數賦回原數組，不能改變起始位置
	{
		p[k] = b[i];
		i++;
		n++;
	}
}