[알고리즘] 합병 정렬 (Merge Sort, 개념과 장단점, 과정, 자바 코드 구현, 시간복잡도, 공간복잡도)

목차

• 합병 정렬이란?
• 합병 정렬 과정
• 합병 정렬 구현 (자바 코드)
• 시간복잡도
• 공간복잡도
• 정렬 알고리즘 비교

 

---

1. 합병 정렬이란?

하나의 배열을 두 개의 균등한 배열로 분할해 정렬하고, 두 배열을 다시 합하여 정렬한다. 큰 문제를 작은 단위의 문제들로 쪼개어 해결해가는 방식인 분할 정복을 이용한 정렬 알고리즘이다.

 

(특징)

• 배열을 이용할 경우 추가적인 메모리가 필요하지만, 연결리스트를 이용할 경우에는 필요하지 않다.
• 최선, 평균, 최악의 시간복잡도는 모두 O(n log(n))이다.

 

(장점)

• 연결리스트를 이용할 경우, 링크 인덱스만 변경하면 되므로 이동 연산이 줄어든다. (추가적인 메모리 필요 X)
• 퀵 정렬과 비교했을 때 데이터 분포에 영향을 받지 않는다.

(단점)

• 배열을 이용할 경우, 추가적인 메모리(임시 배열)이 필요하다.
• 이동 연산이 많아, 레코드 개수가 클 경우에는 비효율적이다.

 

---

2. 합병 정렬 과정

1) 정렬되지 않은 배열을 두 개의 배열로 분할(Divide)한다.

 

2) 분할된 배열의 크기가 0 또는 1이 될때까지 (1)번 과정을 반복한다.

 

3) 부분 배열(Conquer)을 정렬한다.

 

4) 정렬된 부분 배열을 결합(Combine)하고, 부분 배열이 1개가 될 때까지 (3)번 과정을 반복한다. 

 

https://www.geeksforgeeks.org/java-program-for-merge-sort/

 

---

3. 합병 정렬 구현 (자바 코드)

import java.util.*;
import java.io.*;

class Main {
    public static void main (String[] args) throws IOException {
        int[] arr = {5, 2, 2, 9, 100, 70, 11};
        int n = arr.length;

        // 오름차순 정렬
        mergeSort(arr, 0, n-1);

        System.out.println(Arrays.toString(arr));
    }

    private static 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);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] l = Arrays.copyOfRange(arr, left, mid + 1);
        int[] r = Arrays.copyOfRange(arr, mid + 1, right + 1);

        int idx = left;
        int lIdx = 0, rIdx = 0;
        int lLen = l.length, rLen = r.length;

        while (lIdx < lLen && rIdx < rLen) {
            if (l[lIdx] < r[rIdx]) {
                arr[idx++] = l[lIdx++];
            }
            else {
                arr[idx++] = r[rIdx++];
            }
        }

        while (lIdx < lLen) {
            arr[idx++] = l[lIdx++];
        }

        while (rIdx < rLen) {
            arr[idx++] = r[rIdx++];
        }
    }
}

 

---

4. 시간복잡도

데이터의 개수가 n일 때,

• 크기가 n인 배열 분할 : n/2 => n/2 * 1
• 크기가 n/2인 배열 분할 : n/4, n/4 => n/4 * 2
  ...
• 크기가 n/n인 배열 분할 : 1 ... 1 => 1 * n/2

 

배열의 개수가 1개가 될 때까지 분할하므로 n번의 합병이 발생하며, 각 합병 단계마다 원소 개수 만큼의 비교와 이동이 이뤄진다. 배열을 반씩 분할해가며 정렬하기 때문에, log(n)만큼의 비교 연산이 수행된다. 

 

따라서 n번의 합병과 합병 시 log(n)만큼의 연산이 이뤄지므로 최선, 평균, 최악의 시간복잡도는 모두 O(n log(n))를 가진다.

 

---

5. 공간복잡도

데이터의 개수가 n일 때,

 

정렬 과정에서 추가적인 메모리(임시 배열)이 필요하므로 공간복잡도는 O(n)이다.

 

---

6. 정렬 알고리즘 비교 (시간복잡도)