합병정렬(Merge sort)

Sungmin·2023년 5월 18일
0

CS지식

목록 보기
6/6

합병정렬이란?

분할정복 알고리즘의 하나이며 안정 정렬에 속한다.

과정

  1. 리스트의 길이가 0또는 1이면 이미 정렬된 것을 본다.
  2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

특징

  • 단점
    • 만약 레코드를 배열로 구성하면, 임시 배열이 필요
    • 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비 초래
  • 장점
    • 안정적인 정렬 방법
    • 만약 레코드를 연결 리스트로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
    • 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 효율적이다.

시간복잡도

  • O(nlog2n)

profile
Let's Coding

0개의 댓글