배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘 - 교제 242p

• 퀵 정렬과 가장 큰 차이점은 외부에 정렬 작업을 도와 줄 배열을 하나 더 만들어두고 사용한다는 점이다.

✔️ 정렬을 마친 배열의 병합

• 정렬을 마친 두 배열의 병합
• 각 배열에서 선택한 요소의 값을 비교하여 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복하여 정렬을 마치는 배열
• 코드
• 설명

✔️ 병합 정렬

• 정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 한다
• 배열을 앞부분과 뒷부분으로 나눈다
• 나눈 두 배열을 각각 정렬하고 병합하면 배열 모두를 정렬할 수 있다.
• 이때 앞뒤에 놓인 배열을 정렬할 때는 그냥 정렬하는 것이 아니라 다시 병합 정렬을 이용한다.

✔️ 병합 정렬 알고리즘

• 배열의 요소 개수가 2개 이상인 경우

1. 배열의 앞부분을 병합 정렬로 정렬한다
2. 배열의 뒷부분을 병합 정렬로 정렬한다
3. 배열의 앞부분과 뒷부분을 병합한다

• 코드
• 결과
• 설명 : 아직 정리 안됌

✔️ Arrays.sort로 퀵 정렬과 병합 정렬하기

• 제공하는 sort 메소드
• 기본 자료형 배열의 정렬(퀵 정렬)
• 클래스 객체 배열의 정렬(병합 정렬)

✔️ 연습문제

• Q16