병합정렬 간단 정리 (Merge sort)

병합정렬은 데이터를 가장 작은 단위까지 분할한 다음 정렬하면서 다시 병합하는 알고리즘이다.

 

병합정렬의 시간복잡도는  O(N*logN) 이다.  (약 2천만)

 

 

[병합정렬 예시 1]

 

 

[병합정렬 예시 2] :  데이터의 총 개수가 홀수인 경우

 

데이터의 총 개수가 홀수일 경우에는 분할 과정이 남았지만 더 이상 분할할 수 없는 그룹이 존재하게 된다.

이 때는 모든 분할 과정이 끝날 때까지 계속 1개의 원소를 유지합니다.

 

 

 

분할정복 알고리즘 :  하나의 문제를 동일한 유형의 작은 문제들로 분할한 다음에 작은 문제에 대한 결과를 조합해서 큰 문제를 해결하는 방식의 알고리즘

분할 정복 알고리즘은 보통 재귀 함수로 구현된다는 특징이 있다.