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

문제

Merge Sort를 이용하여 int 형 배열을 정렬하시오.

조건

• Arrays.sort 사용 금지
• 병합 정렬을 이용하여 정렬

병합 정렬이란??

우선 입력받은 배열을 길이가 1인 배열이 될 때까지 계속 반으로 나눈다.

나눈 배열을 2개씩 병합하여 정렬한다.

길이가 2인 배열 병합 -> 길이가 4인 배열 병합 -> 길이가 8인 배열 병합 ...

병합할 때마다 요소들을 정렬한다.

해결 방법

'반으로 나눈다 -> 병합한다' 라는 반복과정이 있기 때문에 반복, 재귀 중에 한가지로 해결할 수 있습니다.

저는 재귀를 활용하여 풀었습니다.

배열을 중간을 기준으로 나눠야 하기 때문에 length / 2 를 기준으로 배열을 left, right 두부분으로 분리하였습니다.

배열의 길이가 1이 될 때까지 이과정을 반복해야 하기 때문에 left, right 배열을 초기화하는 과정에서 바로 재귀를 호출하였습니다.

브레이크 포인트로 길이가 1이하가 될 경우 멈추도록 했습니다.

이제 쪼개진 배열을 오름차순으로 병합하면 됩니다.

이때 left 배열과 right 배열은 각각 이미 정렬이 된 상태이기 때문에 두 배열을 앞에서부터 비교하면서 더 작은 쪽의 요소를 넣어주고 인덱스 카운트를 올려줍니다.

그럼 각각의 인덱스를 기억해야하기 때문에 각각 인덱스를 담을 leftIdx, rightIdx를 선언합니다.

그리고 반복문으로 정렬할 배열의 길이만큼 반복해주면서 두 배열 중 작은 요소를 결과 배열에 넣고 해당 배열의 인덱스를 +1 시켜줍니다.

여기서 배열의 길이를 넘어버리면 안되기 때문에 배열의 길이를 넘을 경우 반대쪽 배열의 남은 요소를 모두 붙여넣고 반복을 종료시키도록 합니다.

코드

import java.util.Arrays;

public class MergeSort {
    public int[] mergeSort(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        int middle = arr.length / 2;
        int[] left = mergeSort(Arrays.copyOfRange(arr, 0, middle));
        int[] right = mergeSort(Arrays.copyOfRange(arr, middle, arr.length));

        arr = new int[left.length + right.length];
        int leftIdx = 0;
        int rightIdx = 0;
        for (int i = 0; i < arr.length; i++) {
            if (leftIdx >= left.length) {
                System.arraycopy(right, rightIdx, arr, i, right.length - rightIdx);
                break;
            } else if (rightIdx >= right.length) {
                System.arraycopy(left, leftIdx, arr, i, left.length - leftIdx);
                break;
            } else if(left[leftIdx] > right[rightIdx]) {
                arr[i] = right[rightIdx];
                rightIdx++;
            } else {
                arr[i] = left[leftIdx];
                leftIdx++;
            }
        }
        return arr;
    }
}

깃허브 코드 보러가기

감사합니다. 좋은 하루 되세요. 🤗