leetcode 리트코드 912 머지소트

문제에서 시간 복잡도는 o(nlogn) 으로 끝나야 한다고 제시 했기  때문에, merge sort(병합 정렬)을 사용하면된다.

기본적으로 머지소트는 분할, 정복 개념이 들어간다.

 

구현은 다음과 같다.

1. 좌측, 우측 나눈다.

2. 좌측 끝까지 나눌수 있을때까지 재귀, 우측 끝가지 나눌 수 있을 때 까지 재귀(재귀때는 밑에 구현 함수가 제대로 돈다고 믿고 간다.)

3. 정복(소트)

 

이렇게 된다.

 

분할은 어렵지 않으니 소트만 보면 되는데.

 

이런식으로 정복이된다.

이런식으로 정복이 된다.

1 3 6 7 과 2 3 4 8 정복을 할때를 가정해보자

deque에 첫번째 작업이 끝나면 1 2 3 3 4 6 7이 들어간다.

그렇게 되면 우측에 남게된다. 남은 부분을 deque에전부 밀어주어 deque 에는 1 2 3 4 5 6 7 8 이들어가고.

이 것을 nums 에 넣어주고 리턴한다.

 

 

 

 

class Solution {
    // 시간 복잡도 O(n log n) -> 머지소트 사용
    public int[] sortArray(int[] nums) {
        divide(nums, 0, nums.length-1);
        
        return nums;
    }


    public void divide(int [] nums, int left, int right) {
        // 나눌수 있을 때 까지 나누기
        if (left < right) { 
            int middle = (left+right)/2;
            // 좌측 분할 재귀
            divide(nums, left, middle);

            // 우측 분할 재귀
            divide(nums, middle+1, right);

            // 정복(소트 진행)
            conquer(nums, left, middle, right);
        }

    }

    public void conquer(int [] nums, int left, int middle, int right) {
        Deque<Integer> deque = new ArrayDeque<>();
        int leftCursor = left;
        int rightCursor = middle+1;

        // 좌측커서와 우측커서 기준
        while(leftCursor <= middle && rightCursor <= right) {
            // 좌측 값이 더 작다면 deque에 add
            if(nums[leftCursor] < nums[rightCursor]) {
                deque.addLast(nums[leftCursor]);
                leftCursor ++;
            }
            // 우측 값이 더 작다면 deque에 add
            else {
                deque.addLast(nums[rightCursor]);
                rightCursor ++;
            }
        }

        // 한쪽에 몰려 있으면 다른 한쪽이 끝나지 않기 때문에 나머지 add
        if(leftCursor > middle) {
            while(rightCursor <= right) {
                deque.addLast(nums[rightCursor]);
                rightCursor ++;
            }
        }
        else if(rightCursor > right) {
            while(leftCursor <= middle) {
                deque.addLast(nums[leftCursor]);
                leftCursor ++;
            }
        }

        // deque 를 하나씩 빼주면서 nums 의 값 교체(소트 된 값)
        while(!deque.isEmpty()) {
            nums[left] = deque.pollFirst();
            left++;
        }
    }
}