[알고리즘] 병합정렬_Merge Sort 의 핵심이론

병합정렬 장점 안정적이고 시간복잡도도 좋은 알고리즘이고 코딩테스트에서 병합정렬을 이해하고 응용해서 푸는 문제가 많이 나온다.

이 말은 정렬 관련 문제뿐만 아니라 정렬 아이디어를 가지고 푸는 문제도 많이 나온다는 말이다.

핵심은 2개의 그룹을 병합하는 원리는 꼭 숙지 해야한다는 것이다!

 

투포인터 개념을 사용하여 왼쪽 오른쪽 그룹을 병합하는 것이고 아래 예를 들어 설명을 적어 놓는다.

 

오름차순으로 정렬!

12

53

27

11

5

23

76

67

병합 정렬은 우선 두개씩 그룹으로 합쳐지며 정렬이 된다.(N번)

4개로 나눠진 그룹을 각각 작은값을 왼쪽 큰 값을 오른쪽으로 정렬이 되고 그룹으로 합쳐지면서 정렬이 일어난다.

12

53

11

27

5

23

67

76

오름차순이기에 작은 값이 앞으로 오게된다.

0번 인덱스 : 12 > 11 -> 11

1번 인덱스 : 12 < 27 -> 12

2번 인덱스 : 53 > 27 -> 27

3번 인덱스 : 나머지 53

아래 주황색 데이터가 한 그룹으로 합쳐지고 초록색도 동일한 방법으로 투 포인터를 잡아서 병렬을 진행한다.

(표2)

11

12

27

53

5

23

67

76

 

위와 같이 두개도 순서대로 정렬을 하겠다.

0번 인덱스 : 11 > 5 -> 5

1번 인덱스 : 11 < 27 -> 11

2번 인덱스 : 12 < 27 -> 12

3번 인덱스 : 27 > 23 -> 23

4번 인덱스 : 27 < 67 -> 27

5번 인덱스 : 53 < 67 -> 53

왼쪽 그룹 마지막인 53까지 포인터가 다 갔기 때문에 남은 67, 76 은 순서대로 다음 인덱스로 오게되면 된다.

5

11

12

23

27

53

67

76

과 같이 병합정렬이 되는걸 알 수 있다. 

 

처음 한번에는 N 번의 데이터 접근이 일어나고 N번의 데이터 병합 작업을 logN 번 하기에 시간복잡도는 NlogN 이다.

 

투 포인터를 쓰기에 표2 부분 중간쯤 있는 포인터 5가 제일 앞쪽인 인덱스 0으로 온다.

버블정렬을 사용하게 된다면 5와 swap이 4번 일어나게 되는데 병합정렬은 한번으로 4번 변경이 된다는것을 알 수 있다.

 

시간복잡도가 제한이 nlogn 으로만 풀어야 하는 코딩테스트면 버블정렬이 아닌 병합정렬로 풀어야 하며 해당 문제는 

찾아서 풀어보고 풀이를 공유 할 예정이다. 

그래서 2개의 그룹을 병합하는 과정을 확실히 이해하여야 해당 문제들을 풀수가 있다! 

이 부분은 이해가 될때까지 공부하기!