# 배열리스트를 n/3으로 분할 후 정렬 / 병합
def merge_sort(low, high)
	if (high-low >= 2)
		mid1 = (high-low) /3 + low
		mid2 = ((high-low)*2)/3 + low
		
		merge_sort(low, mid1)
		merge_sort(mid1+1, mid2)
		merge_sort(mid2+1, high)
		merge(low, mid1, mid2, high)
	else
		if (high-low==1 && $a[low] > $a[high])
			tmp = $a[low]
			$a[low] = $a[high]
			$a[high] = tmp
		end
	end
end

def merge(low, mid1, mid2, high)
	i, h, j, m, k = low, low, mid1+1, mid2+1, 0	

	b = []
	pass = false;
	while ((h<=mid1) and (j<=mid2) and (m<=high))
		if ($a[h] <= $a[j] && $a[h] <= $a[m])
			b[i] = $a[h]
			h = h + 1
			i = i + 1
			next	
		end	
		if ($a[j] <= $a[h] && $a[j] <= $a[m])
			b[i] = $a[j]
			j = j + 1
			i = i + 1
			next	
		end
		if ($a[m] <= $a[h] && $a[m] <= $a[j])
			b[i] = $a[m]
			m = m + 1
			i = i + 1
			next	
		end
	end
	# 루프가 종료하고 남은 요소들을 병합
	if (h > mid1 && !pass)
		pass = true
		while ((j<=mid2) and (m<=high))
			if ($a[j] <= $a[m])
				b[i] = $a[j]
				j = j + 1
			else
				b[i] = $a[m]
				m = m + 1
			end
			i = i + 1
		end
		if (j > mid2)
			for k in m..high
				b[i] = $a[k]
				i = i + 1
			end
		else
			for k in j..mid2
				b[i] = $a[k]
				i = i + 1
			end
		end
	end
	if (j > mid2 && !pass)
		pass = true
		while ((h<=mid1) and (m<=high))
			if ($a[h] <= $a[m])
				b[i] = $a[h]
				h = h + 1
			else
				b[i] = $a[m]
				m = m + 1
			end
			i = i + 1
		end
		if h > mid1
			for k in m..high
				b[i] = $a[k]
				i = i + 1
			end
		else
			for k in h..mid1
				b[i] = $a[k]
				i = i + 1
			end
		end
	end
	if (m > high && !pass)
		while ((h<=mid1) and (j<=mid2))
			if ($a[h] <= $a[j])
				b[i] = $a[h]
				h = h + 1
			else
				b[i] = $a[j]
				j = j + 1
			end
			i = i + 1
		end
		if (h > mid1)
			for k in j..mid2
				b[i] = $a[k]
				i = i + 1
			end
		else
			for k in h..mid1
				b[i] = $a[k]
				i = i + 1
			end
		end
	end
    # 원배열에 정련된 임시배열값을 복사	
	for k in low..high
		$a[k] = b[k]
	end
end

#$a = [1,5,4,3,2,6,9,7,8]
$a = Array.new(100)
$a.each_index { |i| $a[i] = rand(100)+1 }

$a.each { |x| print x, " " }
merge_sort(0,99) 

print "결과\n"
$a.each { |x| print x, " " }

#include <iostream>

using namespace std;

void mergeSort(int * a, int low, int high);
void merge(int * a, int low, int mid1, int mid2, int high);
void print(int * arr, int size);
int * minThree(int * a, int *i, int *j, int *k);
int * minTwo(int * a, int *i, int *j);


int main()
{
	int size = 100;
	int * arr = new int[size];

	srand(time(NULL));
	// 초기화- 0~99까지 수를 랜덤으로 복사
	for (int i=0; i < size; i++)
		arr[i] = rand() % size;

	// 정렬 전 
	print(arr, size);

	mergeSort(arr, 0, size-1);
	// 정렬 후 
	print(arr,size);

	return 0;
}


void mergeSort(int * a, int low, int high)
{
	int mid1, mid2;

	if (high-low >= 2)
	{
		mid1 = (high-low)/3 + low;
		mid2 = ((high-low)*2)/3 + low;

		mergeSort(a, low, mid1);
		mergeSort(a, mid1+1, mid2);
		mergeSort(a, mid2+1, high);
		merge(a, low, mid1, mid2, high);
	}
	else
	{	
		if (high-low==1 && a[low] > a[high])
		{
			int tmp = a[low];
			a[low] = a[high];
			a[high] = tmp;
		}
	}
}


void merge(int * a, int low, int mid1, int mid2, int high)
{
	int * b = new int[high-low+1];
	bool pass = false;  // 조건을 만족할 경우 나머지 if문을 통과하기 위한 변수
	int i, h, j, m;
	
	i = 0;
	h = low;
	j = mid1 + 1; 
	m = mid2 + 1;

	// 세분할 배열중 하나를 다 복사할때까지 루프를 돈다
	for (; h<=mid1 && j<=mid2 && m<=high; i++)
	{
		int * p = minThree(a, &h, &j, &m);
		b[i] = a[*p];
		*p = *p + 1;
	}

	if (h > mid1)
	{
		pass = true;
		// 나머지 두 분할 배열중 하나를 다 복사할때까지 루프를 돈다
		for (; j<=mid2 && m<=high; i++)
		{
			int * p = minTwo(a, &j, &m);
			b[i] = a[*p];
			*p = *p + 1;
		}
		// 나머지 하나의 분할배열을 복사한다
		if (j > mid2)
			for (; m<=high; i++, m++)
				b[i] = a[m];
		else
			for (; j<=mid2; i++, j++)
				b[i] = a[j];
	}

	if (j > mid2 && !pass)
	{
		pass = true;
		for (; h<=mid1 && m<=high; i++)
		{
			int * p = minTwo(a, &h, &m);
			b[i] = a[*p];
			*p = *p + 1;
		}

		if (h > mid1)
			for (; m<=high; i++, m++)
				b[i] = a[m];
		else
			for (; h<=mid1; i++, h++)
				b[i] = a[h];
	}

	if (m > high && !pass)
	{
		for (; h<=mid1 && j<=mid2; i++)
		{
			int * p = minTwo(a, &h, &j);
			b[i] = a[*p];
			*p = *p + 1;
		}

		if (j > mid2)
			for (; h<=mid1; i++, h++)
				b[i] = a[h];
		else
			for (; j<=mid2; i++, j++)
				b[i] = a[j];
	}

	// 정렬된 임시배열을 원본배열에 복사한다
	for (int k=low; k <= high; k++)
		a[k] = b[k-low];
	
}

// 배열의 내용 출력
void print(int * a, int size)
{
	for (int i=0; i < size; i++)
		cout << a[i] << " " ;	
	cout << endl;

}


// 세 분할배열에 숫자 중 가장 작은수의 인덱스를 반환
int * minThree(int * a, int *i, int *j, int *k)
{
	if (a[*i]<=a[*j] && a[*i]<=a[*k])
		return i;
	if (a[*j]<=a[*i] && a[*j]<=a[*k])
		return j;
	if (a[*k]<=a[*i] && a[*k]<=a[*j])
		return k;
}

// 두 분할배열에 숫자 중 가장 작은수의 인덱스를 반환
int * minTwo(int * a, int * i, int * j)
{
	if (a[*i]<=a[*j])
		return i;
	else
		return j;
}