c++ in-place merge sort O(n) 간단한 구현

 

 

{ 1,3,5,8,0,0,0,0 } 같은 배열이 있을 때
 { 1,2,3,4 } <- 요 배열을 in-place로 윗 배열에 넣고 정렬할 것이다

 

정렬 결과는 {1,1,2,3,3,4,5,8}과 같이 될 것이다.

 

 

코드 >>

#include <iostream>
#include <vector>
 
 
void merge_sort(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n)
{
    int idx0 = m - 1;
    int idx1 = (int)nums2.size() - 1;
    int idx2 = n - 1;
 
    if (idx2 < 0 && idx1 < 0)
    {
        return;
    }
 
    while ((idx2 >= 0) && (idx1 >= 0))
    {
        if (nums1[idx1] < nums2[idx2])
        {
            nums1[idx0] = nums2[idx2];
            idx2--;
            idx0--;
            std::cout << "idx2-- " << idx2 << std::endl;
        }
        else
        {
            nums1[idx0] = nums1[idx1];
            idx1--;
            idx0--;
            std::cout << "idx1-- " << idx2 << std::endl;
        }
    }
 
    if (idx1 < 0)
    {
        for (; idx2 >= 0; idx2--)
        {
            nums1[idx2] = nums2[idx2];
        }
    }
    
 
}
 
int main()
{
    std::vector<int> nums1 = { 1,3,5,8,0,0,0,0 };
    std::vector<int> nums2 = { 1,2,3,4 };
    merge_sort(nums1, (int)nums1.size(), nums2, (int)nums2.size());
    
    for (const auto& num : nums1)
    {
        std::cout << num << std::endl;
    }
 
    return 0;
 
}