병합정렬(Merge Sort)

병합 정렬(Merge Sort)은
배열을 재귀적으로 반으로 나누고, 각 부분을 정렬한 다음 다시 병합하여 전체 배열을 정렬하는 알고리즘이다.

아래 내용은 배열을 나누고 병합하는 과정을 단계별로 설명한다.

 

주어진 배열

[6, 4, 7, 3, 9, 1, 8]

 

배열을 반으로 나누기 (Divide)

첫 번째 나누기

 [6, 4, 7, 3, 9, 1, 8]
        /         \
[6, 4, 7, 3]     [9, 1, 8]

두 번째 나누기

 [6, 4, 7, 3]       [9, 1, 8]
    /     \           /    \
 [6, 4]   [7, 3]    [9, 1]   [8]
  /  \     /  \      /  \
[6]  [4] [7]  [3]  [9]  [1]  [8]

 

 

배열을 병합하면서 정렬

첫 번째 병합

[6]  [4]     [7] [3]   [9] [1]  [8]
 \  /         \  /      \  /
[4, 6]       [3, 7]    [1, 9]

두 번째 병합

[4, 6]  [3, 7]    [1, 9]  [8]
   \     /          \    /
[3, 4, 6, 7]       [1, 8, 9]

최종 병합

[3, 4, 6, 7]   [1, 8, 9]
      \        /
  [1, 3, 4, 6, 7, 8, 9]

 

병합 정렬 과정

• 1차 분할
  
  • [6, 4, 7, 3]  → 왼쪽 절반
  • [1, 9, 8]     → 오른쪽 절반
• 2차 분할
  • [6, 4, 3, 7]  → 다시 분할
    • [6, 4]  → 왼쪽 절반
    • [7, 3]  → 오른쪽 절반
  • [9, 1, 8]  → 다시 분할:
    • [9, 1]  → 왼쪽 절반
    • [8]     → 오른쪽 절반
• 정렬 시작
  • [6, 4]  → 정렬 → [4, 6]
  • [7, 3]  → 정렬 -> [3, 7]
  • 병합 [4, 6]과 [3, 7] → [3, 4, 6, 7]
  • [9, 1]  → 정렬 → [1, 9]
  • 병합 [1, 9]와 [8] → [1, 8, 9]
• 최종 병합
  • 병합 [3, 4, 6, 7]와 [1, 8, 9] → [1, 3, 4, 6, 7, 8, 9]

 

병합 정렬 알고리즘 구현

import java.util.Arrays;

public class MergeSort {
    static int[] buff;

    static void __mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int i;
            int center = (left + right) / 2;
            int p = 0;
            int j = 0;
            int k = left;

            __mergeSort(a, left, center);
            __mergeSort(a, center + 1, right);

            // 정렬 과정 확인
            for (int x : a) {
                System.out.print(x + " ");
            }
            System.out.println();
            
            for (i = left; i <= center; i++)
                buff[p++] = a[i];

            while (i <= right && j < p)
                a[k++] = (buff[j] <= a[i]) ? buff[j++]: a[i++];

            while (j < p)
                a[k++] = buff[j++];

        }
    }

    static void mergeSort(int[] a, int n) {
        buff = new int[n];

        __mergeSort(a, 0,n - 1);

        buff = null;
    }
    
    public static void main(String[] args) {
        int[] x = {6, 4, 7, 3, 9, 1, 8};

        mergeSort(x, x.length);

        System.out.print("정렬된 정수 배열의 결과: ");
        System.out.println(Arrays.toString(x));
    }
}

 

출력 결과

6 4 7 3 9 1 8 
4 6 7 3 9 1 8 
4 6 3 7 9 1 8 
3 4 6 7 9 1 8 
3 4 6 7 1 9 8 
3 4 6 7 1 8 9 
정렬된 정수 배열의 결과: [1, 3, 4, 6, 7, 8, 9]