본문으로 건너뛰기
실습하기

병합 정렬(Merge Sort)이란?

  • 병합 정렬은 배열을 반으로 나누고, 각 부분을 정렬한 다음 병합하는 방식으로 정렬을 수행하는 알고리즘입니다.

키워드​

  • 분할: 배열을 두 부분으로 나눕니다.

  • 정복: 각 부분을 개별적으로 정렬합니다.

  • 병합: 정렬된 부분들을 하나의 배열로 합칩니다.

  • 최악 시간 복잡도: O(nlog n) - 병합 정렬은 원소의 개수에 대해 로그 선형에 비례하는 시간이 소요됩니다.


병합 정렬 단계별 과정​

  1. 분할 단계: 리스트를 두 부분으로 나눕니다. 이 과정은 재귀적으로 계속됩니다.

  2. 정복 단계: 각 부분을 개별적으로 정렬합니다.

  3. 병합 단계: 정렬된 부분 배열들을 하나의 배열로 병합합니다.

  4. 정렬 완료: 모든 부분 배열이 병합되어 완전히 정렬된 배열이 됩니다.


분할 정복 방식의 특징​

  • 재귀적 접근: 문제를 작은 문제로 나누고, 이를 재귀적으로 해결합니다.

  • 효율성: 분할 정복 방식은 대규모 데이터에 높은 효율성을 보입니다.

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!