[자료구조/알고리즘] 합병정렬(merge sort)

합병정렬

- 여러 개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 방법

- 분할 정복(Divide and Conquer)방식으로 설계된 알고리즘

- 문제를 반으로 쪼개 문제를 해결해 나가는 방식 , 분할은 배열의 크기가 1보다 작거나 같을 때 까지 반복한다

- 시간복잡도 : O(nlogn)

정렬 방법

분할

- 현재 배열을 반으로 쪼갠다

- 배열 시작 위치와 종료위치를 입력받아 둘을 더한 후 2를 나눠 그 위치를 기준으로 나눈다

- 쪼갠 배열의 크기가 0이거나 1 일때 까지 반복한다

합병

- 두 배열 A,B의 크기를 비교한다

- 두 배열의 시작 인덱스를 저장한다

- 두 배열의 맨 앞의 값을 비교하여 이 중 작은 값(오름 차순일 경우)을 새 배열에 저장하고 작은값을 추출한 배열의 인덱스를 증가시켜 준다

- 이를 두 배열중 하나의 배열의 끝에 도달할 때 까지 반복한다

- 끝에 도달하지 못한 다른 배열을 순서대로 새 배열에 모두 저장한다

- 완성된 새배열을 원래의 배열에 저장해준다

ex) 사진 예시

Java로 구현한 합병정렬