leet code

2944 - Sort an Array

merge sort로 풀었습니다.

merge 함수를 짜는 부분에서 index 포함관계 때문에 굉장히 여러 번 틀렸습니다.

middle 부분을 middle+1로 해줘야 두 번째 들어가는 소트 함수에서 무한루프를 돌지 않습니다.

그리고 class 내부에서는 참조할 수 있는 클래스 멤버 array가 두 개 있어야 합니다(정렬 전, 정렬 후).

C++ merge sort. time(beats 57.39%), space(beats 34.23%)

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        sorted = nums;
        this->nums = nums;
        sort(0, nums.size()-1);

        return sorted;
    }

private:
    void sort(int idx_start, int idx_end)
    {
        if (idx_end - idx_start <= 0)
        {
            return;
        }

        int idx_middle = (idx_end + idx_start) / 2;
        sort(idx_start, idx_middle);
        sort(idx_middle+1, idx_end);
        merge(idx_start, idx_middle, idx_end);
    }

    void merge(int idx_start, int idx_middle, int idx_end)
    {
        int idx_s = idx_start;
        int idx_m = idx_middle+1;

        int idx_sorted = idx_start;

        while (idx_s <= idx_middle && idx_m <= idx_end)
        {
            if (nums[idx_s] < nums[idx_m])
            {
                sorted[idx_sorted] = nums[idx_s++];
            }
            else
            {
                sorted[idx_sorted] = nums[idx_m++];
            }

            idx_sorted++;
        }

        // append idx_start part
        while (idx_s <= idx_middle)
        {
            sorted[idx_sorted++] = nums[idx_s++];
        }
        // append idx_middle part
        while (idx_m <= idx_end)
        {
            sorted[idx_sorted++] = nums[idx_m++];
        }

        for (int i = idx_start; i <= idx_end; ++i)
        {
            nums[i] = sorted[i];
        }

        return;
    }

    vector<int> sorted;
    vector<int> nums;
};