비교
쓰기
병합

  • 병합 중인 부분
  • 비교 중
  • 다시 씀
  • 병합된 부분

병합 정렬 자세히 알아보기

병합 정렬

병합 정렬은 분할 정복 알고리즘입니다. 목록을 반으로 나누고, 각 절반을 같은 방법으로 정렬한 뒤, 더 작은 맨 앞 값을 거듭 꺼내 정렬된 두 절반을 병합합니다. 절반들이 버퍼 줄로 옮겨졌다가 순서대로 다시 쓰이는 모습을 원하는 속도로 또는 한 단계씩 보고, 비교, 쓰기, 병합 횟수를 세어 보세요. ‘재생’을 눌러 정렬을 보거나, ‘단계’와 ‘뒤로’로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 타일에는 비교, 목록에 다시 쓰기, 병합 횟수가 표시됩니다. 막대 개수와 시작 순서를 고르거나 직접 숫자를 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.

작동 원리

  1. 막대 개수와 시작 순서를 고르세요: 무작위, 거의 정렬됨, 역순, 값 종류 적음. 직접 숫자를 입력해도 됩니다.
  2. ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 정렬의 원하는 지점으로 이동합니다.
  3. 각 병합을 지켜보세요. 정렬된 두 절반이 버퍼로 내려가고, 더 작은 맨 앞 값이 하나씩 다시 올라옵니다.

병합 정렬의 원리

값이 하나뿐이면 이미 정렬된 것입니다. 그보다 길면 목록을 두 절반으로 나누고 각 절반을 병합 정렬로 정렬합니다. 그다음 병합합니다. 각 절반의 맨 앞 값을 보고 더 작은 값을 결과로 옮기며, 두 절반이 모두 빌 때까지 반복합니다. 두 절반이 정렬되어 있으므로 결과도 정렬됩니다.

언제나 n log n

반으로 나누기를 거듭하면 약 log₂ n개의 단계가 생기고, 단계마다 병합이 모든 값을 한 번씩 쓰므로, 정렬은 약 n log₂ n번 쓰고 비교는 많아야 그만큼 합니다. 버블 정렬, 선택 정렬, 삽입 정렬과 달리 n²으로 늘지 않고, 목록의 순서도 훨씬 덜 중요합니다. 대가는 목록만큼 긴 버퍼입니다. 병합 정렬은 안정 정렬이기도 해서 Python과 Java 정렬의 바탕이 됩니다.

자주 묻는 질문

병합 정렬은 어떻게 동작하나요?

목록을 반으로 나누고, 각 절반을 병합 정렬로 정렬한 뒤, 두 맨 앞 값 중 더 작은 값을 거듭 꺼내 정렬된 두 절반을 병합합니다. 값이 하나인 목록은 이미 정렬되어 있으므로 나누기는 거기서 멈춥니다.

병합 정렬은 비교를 몇 번 하나요?

값 n개에 대해 많아야 약 n log₂ n − n + 1번, 적어도 n log₂ n의 약 절반입니다. 값 40개라면 많아야 177번입니다. 목록에 다시 쓰는 횟수는 n이 같으면 항상 같습니다. 병합 단계마다 값 하나당 한 번입니다.

병합 정렬은 왜 추가 메모리가 필요한가요?

두 절반을 제자리에서 빠르게 병합하기는 어렵기 때문에, 보통의 병합 정렬은 절반들을 버퍼로 복사한 뒤 순서대로 다시 씁니다. 버퍼는 목록만큼 길며, 이것이 퀵 정렬이나 힙 정렬에 비해 가장 큰 단점입니다.

병합 정렬은 안정 정렬인가요?

네. 두 맨 앞 값이 같으면 왼쪽 절반의 값이 먼저 가므로, 같은 값들은 원래 순서를 유지합니다.

제 숫자가 어딘가로 전송되나요?

아니요. 정렬은 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동