contra

아는 만큼 Merge Sort

2020-08-22

Merge Sort는 정렬하고 싶은 데이터를 잘개 쪼갠 다음, 합치면서 정렬하는 방법이다.

[5,3,6,1,2]

이렇게 길이가 5인 데이터가 있다고 가정하면, 길이가 1이 될때까지 무한히 나누는 것을 반복한다.

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

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

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

우선 맨 처음 반으로 나누고, 그 반으로 나누어진 배열 안에서도 다시 반으로 나누고, ... 그래서 더 이상 나눌 수 없는 상태가 될 때까지 그 과정을 반복한다.

데이터를 더 이상 반으로 나눌 수 없다면 데이터의 갯수가 단 2개 뿐이니 서로 비교가 가능할 것이다. 이 때, 두 데이터를 합치면서 서로 대소를 비교하면서 순서를 맞추는 과정을 반복한다.

예를 들어서, 위 예제에서 왼쪽 배열인 [5,3,6] 을 예시로 들어보겠다. 우선 그 배열을 반으로 나누어서 [5,3], [6] 이 될것이고, 다시 [5,3] 을 반으로 나누면 [5], [3] 이 될것이다. [5]와 [3] 은 길이가 1 이므로 더 이상 나눌 수 없다. 이제는 그 두 array를 비교해서 정렬된 하나의 array로 만들어야 한다.

이 때 합치는 과정이 중요하다. 우선 각각 [5] 와 [3], 두 array를 파라메터로 받는다. 그리고 합쳐진 결과를 저장할 임시 array를 만든다. 그리고 두 array를 각각 순환하면서 각각의 array index를 가르키는 포인터 정수 i=0, j=0 를 초기화한다. 두 array의 각 요소 중에 더 작은 값이 tmp array로 오면서 i 또는 j를 한 칸씩 옮기는 과정을 반복한다. 그러면 i 나 j를 이용해 각각의 array의 끝에 도달했는지 알 수 있게 된다. 만약에 어느 한 array의 끝에 도달한다면, 다른 array는 tmp array로 그대로 옮겨주면 된다. 그리고 합쳐진 상태의 임시 array를 저장한다.

실행 순서를 적어보면 대략 이렇다.

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

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

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

[3, 5] -> [5], [3] 합침

[3, 5, 6] -> [3,5], [6] 합침

[1, 2] -> [1], [2]

[1,2,3,5,6] -> [3,5,6], [1,2] 합침