병합 정렬 (Merge sort)에 대한 선입견 없애기

Merge sort는 본래 이미 정렬된 두 개 이상의 배열을 하나의 정렬된 배열로 만드는 것으로
일반적으로 알고 있는 사실이다.

그러나, 정렬되지 않은 하나의 배열을 정렬하는데도 사용할 수 있다는 사실~~~!!!
정렬되지 않은 하나의 배열의 각 원소(인자) 값을 이미 정렬된 배열로 가정하여 2개씩 병합을 하면 된다.

다음과 같은 값들이 입력되었다고 하자.

입력값 :

26

5

77

1

61

11

59

15

48

19

이들의 병합과정은 다음과 같다.

Pass 1 :	[26]	[5]	[77]	[1]	[61]	[11]	[59]	[15]	[48]	[19]
	↘	↙	↘	↙	↘	↙	↘	↙	↘	↙
Pass 2 :	[5	26]	[1	77]	[11	61]	[15	59]	[19	48]
	↘		↙		↘		↙		↓
Pass 3 :	[1	5	26	77]	[11	15	59	61]	[19	48]
	↘				↙				↓
Pass 4 :	[1	5	11	15	26	59	61	77]	[19	48]
	↘								↙
Pass 5 :	[1	5	11	15	19	26	48	59	61	77]