병합 정렬 (merge sort)

김신·2023년 1월 28일

알고리즘

목록 보기

6/7

병합 정렬

합병 정렬 또는 병합 정렬은 O(n log n)의 비교 기반 정렬 알고리즘입니다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나입니다. 존 폰 노이만이 1945년에 개발했습니다.

Divide and conquer

병합 정렬의 근간은 divide and qonquer입니다. 분할 정복은 문제를 작은 문제로 쪼개고 그 후 다시 조합하여 큰 문제를 해결하는 것입니다. 병합 정렬 개념의 시작은 이 분할로 시작해서 합치는 것으로 정복됩니다.

분할 이미지

정복 이미지

구현

구현은 크게 2가지 단계로 이루어집니다. 분할과 정복입니다.

분할

가장 먼저 해야할 작업은 분할입니다. 배열을 계속 양분하다 보면 하나의 원소만 갖게 됩니다. 분할은 그때까지 이루어집니다.

void mergeSort(int arr[], int left, int right) {
 
    if(left==right) return;  
    
    int mid = (left + right) / 2;
    
    mergeSort(arr, left, mid); 
    mergeSort(arr, mid + 1, right); 
    
    merge(arr, left, right);
     
}

병합

병합은 분할이 다 이루어진 이후에 진행됩니다. 하나의 원소가 남은 배열끼리 합치기 시작하면서 원소를 정렬합니다.

void merge(int arr[], int left, int right) {
     
    int L, R, k, a;
    int mid = ( left + right ) / 2;
    L = left;
    R = mid + 1;
    k = left;
    
    // 1
 
    while (L <= mid && R <= right)
        tmp[k++] = arr[L] <= arr[R] ? arr[L++] : arr[R++];
        
  	// 2
 
    if (L>mid) 
        for (a = R; a <= right; a++)
            tmp[k++] = arr[a];
    else
        for (a = L; a <= mid; a++)
            tmp[k++] = arr[a];
            
    // 3
    
    for (a = left; a <= right; a++) 
        arr[a] = tmp[a];
     
}

위 코드와 아래의 그림을 함께 보면 이해가 더욱 쉽습니다.

arr[L]과 arr[R]을 비교해서 더 작은 숫자를 임시 배열 tmp에 채워 넣습니다.

위에서 arr[L]을 tmp에 채워 넣었기 때문에 arr[L+1]과 arr[R]을 비교합니다. 그리고 더 작은 값을 tmp 배열에 채워 넣습니다.

위 과정을 반복합니다.

왼쪽 배열의 범위를 넘어 섰으니 while의 조건식이 false를 반환합니다. while문이 종료되고 오른쪽 배열에 아직 tmp에 채워 넣지 않은 원소가 있으므로 남은 원소를 처리하는 과정을 거칩니다.

tmp에 채워 넣지 않은 원소가 모두 tmp에 넣는 작업이 끝나면 정렬된 tmp원소를 그대로 arr에 옮겨주는 작업을 합니다.

요약

하나의 배열을 L과 R을 기준으로 나누었다고 생각하면 좋습니다. 왼쪽 배열과 오른쪽 배열이 정해진 인덱스를 넘기 전까지 while문을 반복합니다. 이 반복문을 통해 오름차순으로 정렬을 위한 임시 배열을 채워 넣습니다.
왼쪽과 오른쪽 배열 중 하나라도 범위를 넘어선다면 while문이 종료가 됩니다. 남은 한 쪽 배열의 원소 또한 오름차순을 위해 tmp 배열에 채워 넣는 작업을 시도합니다.

이제 tmp에는 양쪽 배열의 원소들을 오름차순으로 정렬한 것으로 채워져있습니다. tmp는 우리가 최종적으로 내놓을 결과물이 아니기 때문에 tmp원소의 순서대로 arr에 채워 넣는 작업을 합니다.

전체 코드 with C

#include <stdio.h>
#define SIZE 5
int tmp[SIZE];
                     
void merge(int arr[], int left, int right) {
     
    int L, R, k, a;
    int mid = (left + right) / 2;
    L = left;
    R = mid + 1;
    k = left;
 
    while (L <= mid && R <= right)
        tmp[k++] = arr[L] <= arr[R] ? arr[L++] : arr[R++];
 
    if (L>mid) 
        for (a = R; a <= right; a++)
            tmp[k++] = arr[a];
    else
        for (a = L; a <= mid; a++)
            tmp[k++] = arr[a];
     
    for (a = left; a <= right; a++) 
        arr[a] = tmp[a];
     
}
 
 
void mergeSort(int arr[], int left, int right) {
     
    if (left == right) return;
    int mid;
    mid = (left + right) / 2;
    mergeSort(arr, left, mid); 
    mergeSort(arr, mid + 1, right); 
    merge(arr, left, right); 
     
}
void printArr(int arr[], int size) {
    int i;
    for (i = 0; i<size; i++) 
        printf("%d ", arr[i]);
     
    printf("\n");
}
void main() {
    int i;
    int arr[SIZE] = { 3,4,1,5,2 };
 
    mergeSort(arr, 0, SIZE - 1);
    printArr(arr, SIZE);
}