[C++][STL] sort

LeetCode : Sort an Array 문제를 풀다가 의문점이 생겼다.

 

제약조건은 다음과 같다.

• 1 <= nums.length <= 5 * 10^4
• -5 * 104 <= nums[i] <= 5 * 10^4

즉, nlog(n)으로 sorting해야하는 간단한 문제다.

근데 C++의 STL인 sort는 내부적으로 quick sort를 사용한다는데 어떻게 STL을 사용해 통과했을까?

quick sort는 최악의 경우 O(N^2)이다.

 

당연히, merge sort 같은 O(Nlog(N))을 사용해야할 줄 알았다.첫번째 풀이 merge sort다.

class Solution {
    public:
    void mergeSort(vector<int>& nums, int s, int e) {
        if (s != e) {
            int mid = (s+e)/2;
            mergeSort(nums, s, mid);
            mergeSort(nums, mid+1, e);
            merge(nums, s, mid, e);
        }
    }
    void merge(vector<int>& nums, int s, int m, int e) {
        int i = s;
        int j = m+1;
        int k = e;
        vector<int> tmp;
        while(i <= m && j <= e) {
            if (nums[i] < nums[j]) {
                tmp.push_back(nums[i++]);
            }
            else {
                tmp.push_back(nums[j++]);
            }
        }

        while (i <= m) {
            tmp.push_back(nums[i++]);
        }
        while (j <= e) {
            tmp.push_back(nums[j++]);
        }

        for (int i = s; i <= e; i++) {
            nums[i] = tmp[i-s];
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size()-1);
        return nums;
    }
};

Runtime: 133 ms

 

두번째 풀이, sort STL이다.

class Solution {
    public:
    vector<int> sortArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums;
    }
};

Runtime: 22 ms

 

성공했다. 심지어 시간도 훨씬 빠르다.

테스트 케이스도 1~50000의 정렬된 vector를 넣어봤다.

 

왜 되는 걸까?

내부적으로, sort는 단순히 quick sort가 아니라 최악의 경우를 대비한 로직이 있다고 한다.

따라서 문제풀때는 닥치고 sort쓰면 된다.