병합정렬(Merge sort) 알고리즘

병합정렬 풀이

배열을 절반으로 나누어 정렬하고 나눈 두 개를 합쳐서 재정렬하는 방법.
원소가 1개가 될때까지 절반으로 나눔.
임시저장할 배열공간이 필요하기 때문에 공간의 제약이 있음.

[4, 2, 5, 8, 6, 1, 3, 9]

[4, 2, 5, 8], [6, 1, 3, 9]

[4, 2], [5, 8], [6, 1], [3, 9]

[4], [2], [5], [8], [6], [1], [3], [9]

4, 2 값을 비교하여 작은값 먼저 새로운 배열에 넣음.

[4], [2]

[2, 4]

5, 8 값을 비교하여 작은값 먼저 배열에 넣음.

[5],[8]

[5, 8]

1개짜리 배열이 다 돌면 이렇게 된다
[2, 4, 5, 8, 1, 6, 3, 9]

이제 2개짜리 배열을 비교
[2, 4]

[5, 8]

2를 넣고 배열인덱스+1 해줌.

[2, 4]

[5, 8]

비교할 배열이 모두 소진되었으므로 그대로 남은 배열을 넣어줌
[2, 4, 5, 8]

2개짜리 배열이 다 돌면 이렇게 된다

[2, 4, 5, 8, 1, 3, 6, 9]

이런식으로 진행되므로 재귀함수를 사용하여 코드를 작성.

코드작성

public class MergeSort {

    private static final Integer[] targetArray = {4, 2, 7, 9, 5, 8 ,1, 3};
    private static final Integer[] tempArray = new Integer[targetArray.length];

    public static void main(String[] args) {
        mergeSort(0, targetArray.length - 1);
    }

    private static void mergeSort(int startIndex, int endIndex) {
        if(startIndex < endIndex) {
            int middleIndex = (startIndex + endIndex) / 2;
            mergeSort(startIndex, middleIndex);
            mergeSort(middleIndex+1, endIndex);

            mergeArray(startIndex, middleIndex, endIndex);
        }
    }

    private static void mergeArray( int startIndex, int middleIndex, int endIndex) {
        int countIndex = startIndex;
        for (int i = startIndex; i <= endIndex; i += 1) {
            tempArray[i] = targetArray[i];
        }

        int leftPointer = startIndex;
        int rightPointer = middleIndex + 1;

        while(leftPointer <= middleIndex && rightPointer <= endIndex) {
            if(tempArray[leftPointer] <= tempArray[rightPointer] ) {
                targetArray[countIndex++] = tempArray[leftPointer++];
            } else {
                targetArray[countIndex++] = tempArray[rightPointer++];
            }
        }

        for(int i = 0 ; i <= middleIndex - leftPointer; i += 1) {
            targetArray[countIndex + i] = tempArray[leftPointer + i];
        }
        System.out.println(":::::::targetArray:::::::"+Arrays.toString(targetArray));
    }
}