정렬(Sorting) - 합병 정렬 (Merge Sort)

합병 정렬 (Merge Sort)

이미 정렬된 리스트 2개 → 1개의 정렬된 리스트

시간 복잡도 : O(n-l+1) .  [ n-l+1 = 원소 수]

init List	3	4	8	10	2	6	8	9
	↑ l			↑ m	↑ m+1			↑ n
	i1				i2
merged List	2	3	4	6	8	8	9	10

 

 

 

반복 합병 정렬

입력 열의 길이가 1인 n개의 정렬된 List를 합병하여 길이가 2인 List 생성

길이가 2인 n/2개의 List를 합병하여 길이가 4인 List 생성

길이가 n인 List로 최종 합병될 때까지 계속