[java] 병합 정렬 알고리즘

04 Dec 2023

java

병합 정렬은 대표적인 정렬 알고리즘 중 하나로, 분할 정복 기법을 사용하여 구현됩니다. 이 알고리즘은 배열을 반으로 나누고, 나뉜 부분 배열을 재귀적으로 정렬한 후, 정렬된 부분 배열을 다시 병합하여 최종적으로 정렬된 배열을 만들어냅니다.

알고리즘 설명

병합 정렬 알고리즘의 주요한 두 단계는 분할(Divide)과 병합(Conquer) 단계입니다.

분할 단계: 입력 배열을 반으로 나눕니다. 이를 위해 입력 배열의 중간 지점을 찾고, 중간을 기준으로 왼쪽 부분 배열과 오른쪽 부분 배열로 분할합니다.
정복 단계: 분할된 부분 배열들을 재귀적으로 정렬합니다. 이는 새로운 배열을 생성하지 않고, 주어진 배열 안에서 진행됩니다.
병합 단계: 정렬된 부분 배열들을 병합하여 하나의 정렬된 배열을 생성합니다. 이 때, 병합하는 과정에서 두 부분 배열의 원소를 비교하여 작은 순서대로 새로운 배열에 저장합니다.

위의 세 단계를 재귀적으로 반복하다 보면, 입력 배열은 계속해서 반으로 나뉘고, 정렬된 부분 배열들이 병합되면서 최종적으로 정렬된 배열을 얻을 수 있습니다.

시간 복잡도

병합 정렬의 시간 복잡도는 O(n log n)입니다. 이는 분할 단계에서 배열을 반으로 나누는 과정이 log n번 발생하고, 각 단계에서 병합하는 과정에서 최악의 경우 n개의 원소를 비교해야 하기 때문입니다. 따라서 평균적으로 n(log n)의 비교 연산이 필요하므로, 시간 복잡도는 O(n log n)이 됩니다.

자바로 구현한 병합 정렬 예제 코드

public class MergeSort {
  
  public void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int[] L = new int[n1];
    int[] R = new int[n2];

    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0;

    int k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
  }

  public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
  
        merge(arr, left, mid, right);
    }
  }

  public static void main(String[] args) {
    int[] arr = {64, 34, 25, 12, 22, 11, 90};
    int n = arr.length;

    MergeSort ms = new MergeSort();
    ms.mergeSort(arr, 0, n - 1);

    System.out.println("정렬된 배열:");
    for (int i = 0; i < n; ++i) {
        System.out.print(arr[i] + " ");
    }
  }
}

위 예제는 자바로 병합 정렬을 구현한 코드입니다. 입력 배열을 정렬하는 mergeSort 메소드와 병합하는 merge 메소드를 포함하고 있습니다. mergeSort 메소드는 분할하는 과정을 담당하며, merge 메소드는 정렬된 부분 배열을 병합하는 과정을 담당합니다. main 메소드에서는 예시로 주어진 배열을 정렬하고, 정렬 결과를 출력하는 기능을 담당합니다.

알고리즘 설명

시간 복잡도

자바로 구현한 병합 정렬 예제 코드

참고 자료