합병 정렬 (Merge Sort)

특징

• 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식
• O(nlogn)

정렬 과정

합병 과정에서는 추가 저장을 위한 메모리가 필요하다

소스코드

• 쪼개고 합쳐지는 과정을 인덱스를 통해 구분하는 것으로 구현한다.
• 인덱스를 더 짜를 수 없을 때까지 짜른 뒤, p와 q를 크기 비교하면서 더 작은 것을 먼저 temp에 넣는다.
• 재귀를 통해 나눠진 부분들을 정렬해가면서 합치는 것을 구현한다.

// 합병 정렬

import java.util.Arrays;

public class Main {

    //쪼개는 메소드
    public static void mergeSort(int[] arr, int[] tmp, int left, int right) {
        if (left < right) { //left가 right보다 작으면(= 더 쪼개질게 있으면)
            int mid = (left + right) / 2;   //쪼개는 기준이 되는 중간 인덱스

            //arr과 tmp는 똑같이 그냥 입력되고, 인덱스를 나누기만 하는것
            mergeSort(arr, tmp, left, mid); //중간 인덱스 앞쪽
            mergeSort(arr, tmp, mid + 1, right);    //중간 인덱스 뒤쪽

            //arr 값을 쪼개진 인덱스를 가지고 tmp에 넣는것. 이 과정 때문에 mergeSort 매개변수로 arr과 tmp가 있다
            merge(arr, tmp, left, right, mid);
        }
    }

    //합치는 메소드
    public static void merge(int[] arr, int[] tmp, int left, int right, int mid) {
        int p = left;
        int q = mid + 1;
        int idx = p;
        // p, q 둘 중 하나는 해당 배열 범위 안에 있는 동안(=처리해야할 값이 남아있는 동안)
        while (p <= mid || q <= right) {
            if (p <= mid && q <= right) {   // 둘 다 범위 안인 경우(=양쪽 다 값이 남아있는 경우)
                if (arr[p] <= arr[q]) { // 왼쪽 영역과 오른쪽 영역 값 비교하여 작은 값을 tmp에 넣어줌
                    tmp[idx++] = arr[p++];
                } else {
                    tmp[idx++] = arr[q++];
                }
            } else if (p <= mid && q > right) { // 왼쪽만 남은 경우 tmp에 넣어줌
                tmp[idx++] = arr[p++];
            } else {                            // 오른쪽만 남은 경우 tmp에 넣어줌
                tmp[idx++] = arr[q++];
            }
        }

        for (int i = left; i <= right; i++) {   // 정렬된 부분 데이터 arr 쪽으로
            arr[i] = tmp[i];
        }
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {3, 5, 2, 7, 1, 4, 6};
        int[] tmp = new int[arr.length];
        mergeSort(arr, tmp, 0, arr.length - 1);
        System.out.println("합병 정렬: " + Arrays.toString(arr));
    }
}