분할 정복을 이용한, 병합 정렬(merge sort) in C++

#include <iostream>
using namespace std;
int n, a[101], temp[101];

void divide(int lt, int rt) {
	if(lt < rt) {
		int mid, p1, p2, p3;
		mid = (lt+rt)/2;
		divide(lt, mid);
		divide(mid+1, rt); 
		p1 = lt;
		p2 = mid + 1;
		p3 = lt;
		while(p1 <= mid && p2 <= rt) {
			if(a[p1] > a[p2]) temp[p3++] = a[p2++];
			else temp[p3++] = a[p1++];
		}
		while(p1 <= mid) temp[p3++] = a[p1++];		// 한쪽이 먼저 끝나서, 남아있는 경우 
		while(p2 <= rt) temp[p3++] = a[p2++];
		for(int i=lt; i<=rt; i++) {		// a배열을 재배치 
			a[i] = temp[i];
		}
		
	}
}
int main() {
	freopen("input.txt", "rt", stdin);
	cin >> n;
	for(int i=1; i<=n; i++) {
		cin >> a[i];
	}	
	divide(1, n);
	
	for(int i=1; i<=n; i++) {
		cout << a[i] << " ";
	}
	return 0;
}

• divide함수 : 배열의 크기가 1이 될때까지, 연속적으로 분할한 뒤, 오름차순 내림차순의 기준에 의하여 원래의 배열크기까지 병합하는 역할을 한다.
• 시간복잡도 : nlogn
  ex)
  5
  13 5 11 7 23