분할정복

	합병 정렬	퀵 정렬
공통점	주어진 리스트를 두 개로 분할하고, 각각을 정렬
차이점	분할할 때, 단순하게 두 부분으로 나눔	분할할 때, 기준 아이템(Pivot Item)을 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킴
	각 부분 정렬이 끝난 후, '합병'이란 후처리 작업이 필요	각 부분 정렬이 끝난 후, 후처리 작업이 필요로 하지 않음

 

퀵 정렬의 최악의 시간 복잡도는 O(n^2)

평균 복잡도는 nlogn