알고리즘 Part 4

template <typename Type>
void Merge_without_Recursion(Type* _array, int _n) {
    int p, i, _first, _mid, _last;
 
    for (p = 1; p <= _n; p *= 2) {
        // 1, 2, 4, 8, ...
        for (i = 0; i < _n; i += 2*p) {
            // (first, mid, last)
            // (0, 1 ,2)
            // (2, 3, 4) ...
            // ...
            // (0, 4, 8) ...
            // Bottom to Top method
            _first = i;
            _last = min(_first + 2*p, _n);
            _mid = min(_first + p, _n);
            Type* temp = new Type[_last - _first];
            Merge<Type>(&(_array[_first]), &(_array[_mid]), _mid - _first, _last - _mid, temp);
            for (int i = 0; i < _last - _first; i++) {
                _array[_first + i] = temp[i];
            }
            delete[] temp;
        }
    }
}