[JAVA/자료구조] 합병 정렬(Merge Sort)

---

평균 수행 시간이 O(logN)인 알고리즘

• 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort)
• 한번 수행될때 마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우 사용한다.
• 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요하다.

합병 정렬(Merge Sort)

• 비교 기반 정렬 알고리즘
• 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
• 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
• 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다 이때 정렬 결과가 임시 배열에 저장된다.
• 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.

 

합병 정렬(Merge Sort) 구현

합병 정렬(Merge Sort) 구현 결과

[0] : 10 [1] : 20 [2] : 30 [3] : 40 [4] : 70 [5] : 90