알고리즘 개념 7. 병합정렬 Merge sort

개념

두개로 나누고 각각을 해결한 다음, 결과를 모아 원래의 문제를 해결한다.

두 개로 나눈 리스트를 재귀적으로 합병정렬을 이용해 정렬하고, 나중에 다시 합친다.

 

글로는 잘 이해가 안가니까 사진 참고.

분할 -> 정복(정렬) -> 병합

 

 

이때 걸리는 시간?

 O(n log n) 의 시간복잡도를 갖는다.

 

장점?

- 데이터 특성과 상관없이 같은 양이면 정렬시간은 비슷하다.

- 각각의 레코드를 Linked list 로 구성하면, 데이터 이동은 엄청 작아진다. 따라서 크기가 큰 것을 정렬할때 연결리스트를 사용한다면 매우 효율적이다.

 

단점?

- 레코드가 Array면 임시배열이 필요하고, in-place sorting이 아니다

- 크기가 크면 이동횟수가 많아서 비효율적이다. 

 

 

** Stable sort, Unstable sort, Inplace algorithm 나중에 추가로 보기