병합 정렬 ( merge sort )

코드

---

#include <iostream>

using namespace std;

// list 라고 이름 붙인 변수에 주소값이 들어있으니 * 로 값을 가져온다.
void merge(int* list, int left, int mid, int right)
{
	int sorted[8];
	
	int i = left;
	// 두 번째 배열의 시작점
	int j = mid+1;
	int k = left;

	while(i<=mid && j<=right)
	{
		if(list[i] < list[j])
			sorted[k++] = list[i++];
		
		else
			sorted[k++] = list[j++];
	}
	
	while(i<=mid)
		sorted[k++] = list[i++];
	
	while(j<=right)
		sorted[k++] = list[j++];
	
	for(int i=left; i<k; ++i)
		list[i] = sorted[i];
}

void mergesort(int* list, int left, int right)
{ 
	int mid;
	
	if(left<right)
	{
		mid = (left+right)/2;
		
		mergesort(list, left, mid);
		mergesort(list, mid+1, right);
		
		merge(list, left, mid, right);
	}
}

int main(void)
{ 
	int list[8] = {21, 10, 12, 20, 25, 13, 15, 22};
	
	// 배열은 함수에 주소값으로 전달된다.
	mergesort(list, 0, 7);
	
	for(int i=0; i<8; ++i)
		cout<<list[i]<<' ';
}