[C++] 머지 소트(Merge Sort) 구현

크기를 절반씩 나누어 가장 작은 크기부터 정렬을 한 다음

정렬한 배열을 합쳐 다시 정렬하는 분할정복 방식의 알고리즘입니다.

 

그림과 같은 방식으로 정렬이 이루어 집니다.

 

using namespace std;

template <typename T>
class algorithm{
private:
    void swap(T& a, T& b){
        T tmp = a;
        a = b;
        b = tmp;
    }
    void sort(T* array_list, int left, int mid, int right){
        T sorted[right - left];
        int low = left;
        int high = mid;
        int index = 0;
        while(low < mid && high < right){
            if(array_list[low] > array_list[high])
                sorted[index] = array_list[high++];
            else
                sorted[index] = array_list[low++];
            index += 1;
        }
        while(low < mid)
            sorted[index++] = array_list[low++];
        while(high < right)
            sorted[index++] = array_list[high++];
        for(int i = left; i < right; i++){
            array_list[i] = sorted[i - left];
        }
    }
public:
    void merge_sort(T* array_list, int left, int right){
        if(left >= right - 1) return;
        int mid = (left + right) / 2;
        merge_sort(array_list, left, mid);
        merge_sort(array_list, mid, right);
        sort(array_list, left, mid, right);
    }
};