[JAVA] 병합정렬 구현하기

두 배열이 있으면 두배열의 작은 값을 비교하여 배열에 순차적으로 넣는 정렬방법

출처 : https://www.youtube.com/watch?v=QAyl79dCO_k

병합 정렬을 구현하려면

배열을 0번방과 1번방만 있는 상황까지 분할한다
각 배열을 앞서 말한 방법으로 정렬한다
다른 배열과 똑같이 정렬하여 병합한다

 

자바 코드

public class Main {
    public static void main(String[] args){
     int[] arr = {3, 2, 1, 5, 6, 9, 7, 8};
        sort(arr);

        for (int a : arr) {
            System.out.println(a + " ");
        }
    }

    public static void sort(int[] arr) {
        int[] temp = new int[arr.length];
        mergeSort(arr, temp, 0, arr.length - 1);
    }

    public static void mergeSort(int[] arr, int[] temp, int start, int end) {
        // 분할한 배열의 크기가 1이상일 때
        if (start < end) {
            // 반으로 분할할 위치
            int mid = (start + end) / 2;
            // mid를 기준으로 왼쪽 배열을 가지고 다시 분할
            mergeSort(arr, temp, start, mid);
            // mid를 기준으로 오른쪽 배열을 가지고 다시 분할
            mergeSort(arr, temp, mid + 1, end);
            // 분할이 전부 끝난 후 정렬시작
            merge(arr, temp, start, mid, end);
        }
    }

    public static void merge(int[] arr, int[] temp, int start, int mid, int end) {
        // 정렬할 임시 배열안에 원본 배열의 크기와 해당 위치에 값을 대입
        for (int i = start; i <= end; i++) {
            temp[i] = arr[i];
        }
        // 왼쪽 파티션의 시작위치와 오른쪽 파티션의 시작위치
        int part1 = start;
        int part2 = mid + 1;
        // 원본배열의 대입을 시작할 위치
        int index = start;

        // 각 파티션 중 하나가 최대위치에 도달할 때까지 반복
        while (part1 <= mid && part2 <= end) {
            // 왼쪽 파티션의 값이 더 작을 경우 원본에 대입
            if (temp[part1] <= temp[part2]) {
                arr[index] = temp[part1];
                part1++;
            }
            // 오른쪽 파티션의 값이 더 작을 경우 원본에 대입
            else {
                arr[index] = temp[part2];
                part2++;
            }
            // 값을 대입한 후 대입할 원본의 위치 한칸이동
            index++;
        }
        // 왼쪽이나 오른쪽 파티션에 남은 값이 있으면 순차적으로 대입
        for (int i = 0; i <= mid - part1; i++) {
            arr[index + i] = temp[part1 + i];
        }

    }

}