Algorithm. 합병정렬

Algorithm 합병(Merge)정렬

합병정렬을 학습하기 위해 선행되어야 할 개념은 재귀(Recursion)함수, 분할정복이다.

재귀함수(Recursion) 함수 : 함수가 자기 자신을 호출하는 것.

분할정복 : 어떤 문제를 해결하기 위해 작은 문제로 분할해서 해결하는 것.

합병(병합)정렬은 분할정복과 재귀함수를 사용하고 있습니다.

합병정렬이란 두 배열을 반으로 쪼개서 두 배열의 제일 앞에 있는 값끼리 비교를 합니다.

그리고 새로운 결과 정렬에 작은 값부터 먼저 채우며 정렬하는 방식입니다.

[2,4,5,7,1,3,6,8] 이란 배열을 먼저 두 배열로 나눕니다.

그리고 두 배열의 가장 앞에 있는 값을 비교합니다.

[2,4,5,7][1,3,6,8]

1이 2보다 더 작기 때문에 새로운 결과 배열에 먼저 저장합니다.

[2,4,5,6][3,6,8][1]

다시 두 배열의 가장 앞에 있는 값을 비교하여 작은 수를 결과 배열에 저장합니다.

[2,4,5,6][3,6,8] => [1,2]

이 과정을 반복하여 최종 결과인 [1,2,3,4,5,6,7,8] 이 반환됩니다.

방금 설명한 과정이 배열 두 개를 merge 하는 함수에 대한 설명이었습니다.

그리고 재귀적으로 사용되는 함수이며 배열을 나누는 division 함수가 아래에 있습니다.

division 함수는 배열의 길이가 2개 이상일 때 배열을 나누어 값을 비교하는 merge 함수를 호출합니다.

배열을 나누었더 하더라도 그 수가 2 이상이면 다시 나눕니다.

이해하기 상당히 까다로운 부분은 오히려 merge 함수 부분입니다.

제일 작은 단위로 쪼개어 left, right 배열의 값이 각각 한 개일 때에는

첫번째 while문 한번 동작, 두번째 or 세번째 while 문 한번이 동작합니다.

left 값, right 값이 한번씩 입력되는 것입니다.

그리고 상위 division으로 올라가 배열의 값이 각각 두배가 되어 2, 2 배열이 된다면 

left.length와 right.length 의 값도 당연이 각각 2가 되고 양쪽 배열이 비교대상이 없을 때까지 3번 반복하게 됩니다.

그리고 나머지 하나의 값이 남았을 때는 두번째 or 세번째 while 문이 동작합니다.

이런 방식으로 제일 작은 단위의 배열부터 총 배열 갯수 / 2 의 비교 단위까지 반복하여 비교를 하게 됩니다.

두 배열의 제일 처음 값끼리 비교를 하는 것,

배열의 크기를 잘라 제일 작은 단위를 만드는 것,

값의 비교가 배열이 커져도 가능해야 한다는 것.

이 세 가지를 적용하는 것이 합병정렬의 키포인트였다고 봅니다.

※ 이번 합병정렬은 이해하기 까다로워 기존 참고사이트 코드를 거의 동일하게 사용하였습니다.

참고사이트: www.zerocho.com/category/Algorithm