Merge Sort (병합정렬)

개념

- 분할 정복 알고리즘을 응용한 정렬

(분할 정복이란 문제를 나눌 수 없을 때까지 나누어서 각각을 풀고 다시 합병하는 과정을 거쳐 문제의 답을 얻는 알고리즘을 말한다.)

- 퀵 정렬보다 전반적으로 속도가 느림

- 데이터 크기만한 메모리가 더 필요

- 데이터의 상태에 영향을 받지 않음

(힙, 퀵 정렬은 같은 값의 데이터가 있으면 순서가 뒤바뀔 수도 있다.

정수형 배열[0] = 100, 배열[10] = 100을 정렬할 때 배열[10]이 배열[0]보다 앞에 오는 경우가 생일 수 있다. 그러나 병합 정렬은 위와 같은 상황이 발생하지 않는다.)

​

정수형 배열 A[9]가 있고 [0]번부터 순서대로 (5,3,1,9,4,2,8,7,6)이 있다고 가정하자.

배열 A의 값들을 정렬하려고 할 경우

 

(5,3,1,9,4,2,8,7,6) -> (5,3,1,9),(4,2,8,7),(6)

배열을 세개로 분할한다.

 

(5,3,1,9),(4,2,8,7),(6) -> (5,3),(1,9),(4,2),(8,7),(6)

다섯개로 분할한다.

 

(5,3),(1,9),(4,2),(8,7),(6) -> (5),(3),(1),(9),(4),(2),(8),(7),(6)

더 이상 분할할 수 없을때까지 분할한다.

 

(5),(3),(1),(9),(4),(2),(8),(7),(6) -> (3,5),(1,9),(2,4),(7,8),(6)

두개씩 비교하여 정렬하고 병합한다.

 

(3,5),(1,9),(2,4),(7,8),(6) -> (1,3,5,9),(2,4,7,8),(6)

다시 두개씩 비교하여 정렬하고 병합한다.

 

(1,3,5,9),(2,4,7,8),(6) -> (1,2,3,4,5,7,8,9),(6)

다시 두개씩 비교하여 정렬하고 병합한다.

 

(1,2,3,4,5,7,8,9),(6) -> (1,2,3,4,5,6,7,8,9)

마지막으로 두개를 비교하여 정렬하고 병합한다.

 

 

RememberCook 9월 28일 정식 출시!