합병정렬 구현 (C++)

vector<int> v;
vector<int> temp;

void merge(int start, int mid, int end)
{
	int first = start;
	int second = mid + 1;
	int length = end - start + 1;
	temp.clear();

	// 두 리스트를 비교하며 임시 배열에 정렬하여 넣기
	int i = 0;
	while (first <= mid && second <= end)
	{
		temp.push_back(v[first] < v[second] ? v[first++] : v[second++]);
		i++;
	}

	// 정렬되지 않고 남은 리스트 찾아서 배열에 마저 넎기
	if (first <= mid)
		for (; i < length; i++)
			temp.push_back(v[first++]);
	else
		for (; i < length; i++)
			temp.push_back(v[second++]);

	// 원래 배열에 적용
	for (int k = 0; start + k <= end; k++)
		v[start + k] = temp[k];
}

void mergeSort(int start, int end)
{
	if (start < end)
	{
		int mid = (start + end) / 2;
		mergeSort(start, mid);		// L분할
		mergeSort(mid + 1, end);	// R분할
		merge(start, mid, end);		// 합병
	}
}

메인에서 아래와 같이 호출

mergeSort(0, N-1);