Merge Sort

Merge Sort 

: 두 개의 sorting된 배열을 비교하여 더 작은것부터 정렬하여 전체 sorting

https://www.geeksforgeeks.org/java-program-for-merge-sort/

int sort(int a[], int n)
{
	int h;
	int b[n];
	h = n/2;
	//copy a[] to b[]
	sort(b,h); // 왼쪽 sorting
	sort(b+h, n-h); //오른쪽 sorting
	// merge two halves in b to a
	return ;
}

 

Proof of invariant

sorting의 정의 (invariant)

• sorting이 끝난 후 배열에 저장된 값들을 b[0], b[1] …b[n-1]라고 부르자 (같은 배열이지만 구별하기 위해)
• 조건 1 : {a[0], a[1], … a[n-1]} = {b[0], b[1] … b[n]} 집합으로 같음
• 조건 2 : b[0] < b[1] … b[n-1] (같은 것이 없다고 가정)

(1) Base : n = 1(P(1))인 경우, 정렬 할 것이 없음 ∴ invariant 성립

(2) Step : P(n-1) → P(n)

P(n-1)이 참이라는 것은

n/2일 때 sort함수가 성립함 → 재귀 호출이 끝난 후, a[0] < a[1] ... a[n/2 -1] & a[n/2] < a[n/2 + 1] ... < a[n-1]이 참이라고 믿음

P(n)일 때, a[0] < a[1] ... < a[n-1]이 성립함 >> merge 알고리즘에 의해 부등호가 성립하는 것

* P(n-1)은 재귀 sort가 성공해서 부등호가 성립하는 것

* P(n)은 merge algorithm 때문에 부등호가 성립하는 것

∴ invariant 성립

(3) Result : invariant가 성립한다. 정렬되어있다. 

 

The Complexity

\(T(n) = n + 2T(n/2) = ... =  O(n log n)\)

\(O(n)\) : 합치는 시간