99클럽 코테 스터디 30일차 TIL 병합 정렬

병합 정렬

• 분할과 정복 방식을 사용해 데이터를 분할하고 분할한 값들을 정렬하며 합치는 알고리즘
  • 분할 정복? -> 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 정렬해야 할 리스트를 계속 분할하여 최대한 작게 쪼갠 후, 부분 리스트에서 인접한 원소들끼리 비교하여 정렬하는 방식
• 정렬 방법
  • 주어진 리스트를 절반으로 분할하여 부분 리스트로 나눈다. (Divide : 분할)
  • 해당 부분 리스트의 길이가 1 이 아니라면 1번 과정을 되풀이한다.
    • 반드시 2개의 부분 리스트로 나눌 필요는 없다.
  • 인접한 부분 리스트끼리 정렬하여 합친다. (Conqure : 정복)
• 병합할 때는 투 포인터 개념을 사용한다.
  • 각 부분 리스트의 맨 앞 원소부터 비교를 진행한다.
  • 각 부분 리스트는 이미 오름차순 정렬이 되어있으므로 추가적인 정렬 과정은 필요 없다.
• 시간 복잡도
  • O(NlogN)
  • 최선, 평균, 최악 모두 같다.

 

728x90

느낀 점

• 시간 복잡도가 O(NlogN)으로 O(N²)인 버블, 삽입, 선택 정렬보다 빠르므로 잘 알아두자.

다음에 학습할 것

• 병합 정렬 직접 구현해 보기

반응형

---

병합 정렬은 꼭 구현해 보자!