[알고리즘] 정렬 알고리즘 4. 병합 정렬 (다른 정렬보다 상대적으로 효율적)

👉  분할 정복(Divide and Conquer)

1. 분할(divide): 큰 문제를 작은 부분 문제(쉬운 문제)로 분할
2. 정복(conquer): 작은 부분 문제를 각각 해결
3. 조합(combine): 해결한 부분 문제의 답을 이용하여 다시 큰 문제를 해결

• 일반적으로 재귀 함수를 이용하여 구현
• 이유? 큰 문제를 작은 문제로 "분할하는 방식이 동일한" 경우가 많기 때문
• 더 이상 쪼갤 수 없는 크기가 될 때까지 계속하여 분할
• 분할 정복의 단점
  • 일반적으로 재귀 함수를 사용한다는 점에서 함수 호출 횟수가 많이 발생
  • 이는 오버헤드(overhead)로 이어진다.

 

👉  병합 정렬(Merge Sort)

• 병합 정렬은 전형적인 분할 정복(divide and conquer) 알고리즘이다.
• 시간 복잡도 O(NlogN)을 보장하는 빠른 알고리즘 중 하나

1. 분할(divide): 정렬한 배열(큰 문제)을 같은 크기의 부분 배열(작은 문제) 2개로 분할
2. 정복(conquer): 부분 배열을 정렬 (작은 문제를 해결)
3. 조합(combine): 정렬된 부분 배열을 하나의 배열로 다시 병합

병합정렬 - 위키피디아

👉  병합 정렬의 동작 방식

• 분할(divide): 분할 작업은 단순히 배열의 크기를 절반으로 쪼개는 것

• 정복(conquer): 두 개의 부분 배열을 "정렬된 하나의 배열"로 만드는 것 
  1. 각 부분의 배열은 이미 정렬된 상태로 본다.
  2. 각 부분 배열에 대하여 첫째 원소부터 시작하여 하나씩 확인
  3. 총 원소의 개수가 N개일 때, O(N)의 시간 복잡도가 요구된다.
• 장점: 최악의 경우에도 O(NlogN)을 보장할 수 있다는 점에서 효율적
• 단점: 일반적인 경우, 정복(conquer) 과정에서 임시 배열이 필요

 

 

 

 

출처: https://fastcampus.co.kr/dev_online_upjscodingtest, https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

합병 정렬 - 위키백과, 우리 모두의 백과사전

 

JavaScript 코딩테스트 131개 예제 & CS지식으로 끝내기 | 패스트캠퍼스