[Algorithm]merge sort 병합정렬

한쪽의 배열의 끝에 먼저 도달했을때 처리를 처음에 빼먹었다가 추가했다. Merge함수는 사실 생각하기 쉽고 

MergeSort함수가 생각하기 어렵다.

 

int* Merge(int * left_array, int left_size, int * right_array, int right_size)
{
    int left_index = 0;
    int right_index = 0;
    int merged_index = 0;
    int* merged_array = (int*)malloc(sizeof(int)*(left_size + right_size));
 
    while (merged_index < left_size + right_size)
    {
        if (right_index >= right_size)
        {
            merged_array[merged_index] = left_array[left_index];
            left_index++;
            //right_index = right_size - 1;
        }
        else if (left_index >= left_size)
        {
            merged_array[merged_index] = right_array[right_index];
            right_index++;
        //    left_index = left_size - 1;
        }
        else
        {
 
            if (left_array[left_index] <= right_array[right_index])
            {
                merged_array[merged_index] = left_array[left_index];
                left_index++;
            }
            else if (left_array[left_index] > right_array[right_index])
            {
                merged_array[merged_index] = right_array[right_index];
                right_index++;
            }
            else
            {
                cout << "error" << endl;
            }
        }
        merged_index++;
    }
    return merged_array;
}

 

재귀함수를 쓸때 재귀함수가 종료되는 조건을 항상 먼저 생각해두자.

병합정렬은 분할정복의 대표적인 예다

int* MergeSort(int * inputArray, int size)
{
    if (size <= 1)
    {
        return inputArray;
    }
    int* left= NULL;
    int* right = NULL;
    int mid = size / 2;
 
    left = MergeSort(&inputArray[0], mid);
    right = MergeSort(&inputArray[mid], size - mid);
 
    return Merge(left, mid, right, size - mid);
    
}