[알고리즘 정렬] 합병 정렬(Merge Sort)

  합병 정렬(Merge Sort)이란 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식입니다. 알고리즘 복잡도는 O(n log n)입니다.

  길이가 1인 배열 상태가 된 이후에는 인접한 부분끼리 값을 비교하여 정렬한 뒤 합칩니다. 데이터를 합치는 과정에서 이를 저장하는 메모리가 추가로 필요합니다. 그러나 속도는 이전의 버블 정렬, 삽입 정렬, 선택 정렬과 같은 정렬에 비해 빠릅니다. 과정은 다음 이미지과 같습니다.

 

이미지 출처: 위키백과, 합병 정렬 항목

 

  합병 정렬 구현 코드

public class Main {
    public static void mergeSort(int[] array, int[] temp, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(array, temp, left, mid);
            mergeSort(array, temp, mid + 1, right);
            merge(array, temp, left, right, mid);
        }
    }
    
    public static void merge(int[] array, int[] temp, int left, int right, int mid) {
        int p = left;
        int q = mid + 1;
        int index = p;

        while (p <= mid || q <= right) {
            if (p <= mid && q <= right) {
                if (array[p] <= array[q]) {
                    temp[index++] = array[p++];
                } else {
                    temp[index++] = array[q++];
                }
            } else if (p <= mid && q > right) {
                temp[index++] = array[p++];
            } else {
                temp[index++] = array[q++];
            }
        }
        for (int i = left; i <= right; i++) {
            array[i] = temp[i];
        }
    }
}

  매개 변수로 배열 array와 배열 temp, 정수형 left와 정수형 right를 받는 mergeSort 메소드를 생성합니다.

  if문에서 left가 right보다 크다면 변수 mid를 생성하고 left와 right를 더한 값을 2로 나눕니다.

  재귀적으로 mergeSort 메소드를 호출하여 순서대로 배열의 왼쪽 부분과 배열의 오른쪽 부분을 분할합니다. 이후 merge 메소드를 호출하여 역순으로 합병합니다.

  merge 메소드는 매개 변수로 배열 array와 배열 temp, 정수형 left와 정수형 right와 정수형 mid를 받습니다.

  데이터를 담을 임시 변수 p, q,  temp 배열에서 인덱스를 다룰 index를 생성합니다.

  while문에서 p는 mid보다 작거나 같고, 또는 q가 right보다 작거나 클 때 반복문을 실행합니다. 이는 array 배열 안에서 인덱스가 유효한 범위 안에 있을 때 실행한다는 뜻입니다.

  if문에서 p와 q 역시  모두 유효한 범위 안에 있는지 확인합니다. 조건을 충족했을 때, 안쪽 if문에서 array의 p 번째 원소가 array의 q 번째 원소보다 작거나 같다면 temp의 index 번째 원소에 array의 p 번째 원소를 추가합니다. 만약 p 번째 원소가  q번째 원소보다 크다면 temp의 index 번째 원소에 array의 q 번째 원소를 추가합니다.

  바깥 if문에서의 다른 조건인 else if에서는 p는 유효한 범위에 있되, q는 오른쪽 끝에 있는 상황입니다. 이때 앞선 과정과 마찬가지로 temp의 index 번째 원소에 array의 p 번째 원소를 추가합니다.

  만약 이번 조건에도 해당하지 않는다면 temp의 index 번째 자리에 array의 q번째 원소를 추가합니다.

  for문에서 left부터 right까지 순회하면서 array의 i번째 원소에 temp의 i번째 원소를 추가합니다. 배열을 복사하는 것입니다.