Merge sort

Divide and conquer

• 문제를 쪼개서 각각 따로 처리한 다음 결과를 합쳐나가는 방법.

Merge

• 배열의 길이가 1이면 정렬이 끝난 것이다.
• 아니라면 배열을 반으로 나눠서 왼쪽과 오른쪽을 따로 정렬한다.
• 둘 다 정렬이 끝나면 merge라는 작업을 통해 배열을 합쳐준다.

Merge operation

• 이미 sorted인 2개의 서브 배열
• 이 2개의 서브 배열의 merge된, 병합된 하나의 결과를 담을 배열
• 와 같이 3개의 배열로 이루어져 있다.

위의 배열과 아래의 배열이 합쳐지는데 sorted를 읽지 않도록 합치는 것이다.

• 배열이 3개인만큼 포인터 역시 3개다.
• 윗쪽 배열을 A 아래쪽 배열을 B라고 했을때 포인터마다 원소를 비교해서 작은쪽을 3번째 배열에 넣는다.

만약 아래와 같이 더이상 비교할 대상이 없을 때는 그대로 옮겨다 복사해주면 된다.

Merge operation의 예제

template <typename Type>
void Merge(Type *_arrayA, Type *_arrayB, int _nA, int _nB, Type *_arrayOut){
    int posA = 0;
    int posB = 0;
    int k = 0;
    while (posA < _nA && posB < _nB){
        if( _arrayA[posA] < _arrayB[posB]){
            _arrayOut[k] = _arrayA[posA];
            posA++;
        } else {
            _arrayOut[k] = _arrayB[posB];
            posB++;
        }
        k++;
    }

    for (; posA < _nA; posA++){
        _arrayOut[k] = _arrayA[posA];
        k++;
    }

    for (; posB < _nB; posB++){
        _arrayOut[k] = _arrayB[posB];
        k++;
    }
}

Merge operation의 단점

• in-place로 동작하지 않는다. → merge를 할 때 항상 새로운 제 3의 배열을 memory allocation해야한다는 점이다.
  • in-plate한 동작은 새로운 공간을 할당하지 않고 작동하는것을 말한다.

Merge sort

• 길이가 8인 배열이 있으면 1에서 4까지, 5에서 8까지의 배열로 나누고 이 나뉜 배열을 재귀적으로 나눈다.
• 이론적으로는 길이가 1이 될 때 까지 나누는것이 맞으나 오버헤드를 고려하여 일정 길이 이하로 나눴을 경우 삽입 정렬 등으로 처리한다.

Merge sort implement

template <typename Type>
void Merge(Type *array, int first, int midpoint, int last){
  //..
}

void Merge_Sort(Type *array, int first, int last){
    if (last - first <= NUM_THRESHOLD){
        Insertion_Sort<Type>(array, first, last);
    }else{
        int midpoint = (first + last) / 2;
        Merge_Sort<Type>(array, first, midpoint);
        Merge_Sort<Type>(array, midpoint, last);
        Merge(array, first, midpoint, last);
    }
}

• 오른쪽 과정 생략

• 정렬 완료