1. 4개의 int형 버퍼중에 3개의 int형 버퍼를 할당한다.
   
   1. 첫번째 버퍼에 1이 들어간다.
      
   2. 두번째 버퍼에 2가 들어간다.
      
   3. 3번째 버퍼에 1+2=3 이 들어간다.
      
   4. 4번째 버퍼에 3이 들어간다.
      
   5. 5번째 버퍼에 3+3=6 이 들어간다.
      
   6. 즉 101번을 루프를 돌면 5050이라는 값이 나와야 한다.
      
2. 4개의 int형 버퍼중에, 이전 결과값이 저장된 버퍼를 제외한 3개를 할당한다.
   
   1. 1번을 반복한다.
      
3. 2개의 버퍼가 모두 찼다면, 이걸 다시 더해서 남는 버퍼에 넣는다.
   
   

#include <iostream> 
#include <vector> 
#include <stdlib.h> 
#include <unistd.h> 
 
using namespace std; 
 
#define BUFSIZE  4 
 
class Buff 
{ 
    private: 
        int currentIdx; 
        vector<int *> LBuf; 
        int *tmpptr; 
 
    public: 
        Buff() 
        { 
            currentIdx = 0; 
        } 
 
        void Set(int *a) 
        { 
            LBuf.push_back(a); 
        } 
 
        void Clear() 
        { 
            LBuf.clear(); 
        } 
 
        // Merged Sort를 한다.  
        // 여기에서는 + 연산을 한다. 
        void SetUnion(int a) 
        { 
            int current = (currentIdx+1)%3; 
            int prev = (currentIdx)%3; 
            int tmp = (currentIdx+2)%3; 
 
            if (*LBuf[prev] != -1) 
            { 
                currentIdx++; 
            } 
            *LBuf[current] = a; 
            *LBuf[tmp] = a + *LBuf[prev];  
            printf("Debug %d + %d = %d\n", *LBuf[current], *LBuf[prev], *LBuf[tmp]); 
            currentIdx ++; 
 
            tmpptr = LBuf[(currentIdx)%3]; 
        } 
 
        // 결과가 저장된 버퍼의 레퍼런스를 넘겨준다. 
        int *GetSumResult() 
        { 
            return tmpptr;  
        } 
 
        int TmpIdx() 
        { 
            return currentIdx; 
        } 
}; 
 
class BufManager 
{ 
    private: 
        int *a; 
        vector<Buff> NodeBuf; 
        int checkIdx; 
 
    public: 
 
        BufManager() 
        { 
            // 버퍼를 4개 할당한다. 
            a = (int *)malloc(sizeof(int) * BUFSIZE); 
            checkIdx = 3; 
        } 
 
        void Run() 
        { 
            Buff lBuff1, lBuff2; 
 
            // 각각의 Buff1에 3개씩의 버퍼의 레퍼런스를 할당한다. 
            for (int i = 0; i < BUFSIZE; i++) 
            { 
                a[i] = -1; 
                if (&a[i] != &a[checkIdx]) 
                { 
                    lBuff1.Set(&a[i]); 
                } 
            } 
            NodeBuf.push_back(lBuff1); 
 
            for (int i = 0; i < BUFSIZE; i++) 
            { 
                a[i] = -1; 
                if (&a[i] != &a[checkIdx]) 
                { 
                    lBuff1.Set(&a[i]); 
                } 
            } 
            NodeBuf.push_back(lBuff2); 
 
            int idxflag = 0; 
            int idx; 
 
            // 2개의 그룹이 있다고 가정하고 루프를 돌렸다.  
            for (int i = 0; i < 2; i++) 
            { 
                Buff Bf; 
                idxflag = i % 2; 
                printf("Node Number %d\n", idxflag); 
                getchar(); 
 
                // 101번의 merged Sort가 이루어진다고 가정한다. 
                for (int k = i; k < 101+i; k++) 
                { 
                    NodeBuf[idxflag].SetUnion(k); 
                } 
 
                // merged Sort가 끝났다면, 버퍼를 초기화 한다. 
                NodeBuf[idxflag].Clear(); 
                checkIdx = NodeBuf[idxflag].TmpIdx(); 
 
                // 2개의 버퍼에 결과값이 만들어졌다면, 이 두개를 다시 Merged sort한다. 
                // 아래의 코드는 SetUnion 메서드를 사용하도록 바꿀 수 있을 것이다. 
                if (i > 0) 
                { 
                    printf("RESULT : %d : %d\n", *NodeBuf[0].GetSumResult(), *NodeBuf[1].GetSumResult() ); 
                    getchar(); 
                } 
 
                // 다음 Level의 Merged Sort를 위해서 3개의 메모리의 레퍼런스를 할당한다.   
                // 이때 이전에 결과값이 있는 메모리는 사용하지 않도록 한다.  
                for (int k = 0; k < BUFSIZE; k++) 
                { 
                    // 주소값이 같지 않을 경우에만 할당한다. 
                    if (&a[k] != NodeBuf[idxflag].GetSumResult()) 
                    { 
                        a[k] = -1; 
                        printf("SET %d\n", k); 
                        Bf.Set(&a[k]); 
                    } 
                } 
                NodeBuf[idxflag?0:1] = Bf; 
                printf("Current Result : %d\n", *NodeBuf[idxflag].GetSumResult()); 
                getchar(); 
            } 
        } 
}; 
 
int main(int argc, char **argv) 
{ 
    BufManager *MyBuff;  
    MyBuff = new BufManager(); 
    MyBuff->Run(); 
} 
 

약간 수정된 코드

동일하게 SetUnion 메서드를 사용하도록 약간 수정했다.

#include <iostream> 
#include <vector> 
#include <stdlib.h> 
#include <unistd.h> 
 
using namespace std; 
 
#define BUFSIZE  4 
 
class Buff 
{ 
    private: 
        int currentIdx; 
        vector<int *> LBuf; 
        int *tmpptr; 
    public: 
         
        Buff() 
        { 
            currentIdx = 0; 
        } 
 
        void Set(int *a) 
        { 
            LBuf.push_back(a); 
        } 
 
        void Clear() 
        { 
            LBuf.clear(); 
        } 
 
        void SetUnion(int a) 
        { 
            int current = (currentIdx+1)%3; 
            int prev = (currentIdx)%3; 
            int tmp = (currentIdx+2)%3; 
 
            if (*LBuf[prev] != -1) 
            { 
                currentIdx++; 
            } 
            *LBuf[current] = a; 
            *LBuf[tmp] = a + *LBuf[prev];  
            printf("Debug %d + %d = %d\n", *LBuf[current], *LBuf[prev], *LBuf[tmp]); 
            currentIdx ++; 
 
            tmpptr = LBuf[(currentIdx)%3]; 
        } 
 
        int *GetSumResult() 
        { 
            return tmpptr;  
        } 
        int TmpIdx() 
        { 
            return currentIdx; 
        } 
}; 
 
class BufManager 
{ 
    private: 
        int *a; 
        vector<Buff> NodeBuf; 
        int checkIdx; 
 
    public: 
 
        BufManager() 
        { 
            a = (int *)malloc(sizeof(int) * BUFSIZE); 
            checkIdx = 3; 
        } 
 
        void Run() 
        { 
            Buff lBuff1, lBuff2; 
 
            for (int i = 0; i < BUFSIZE; i++) 
            { 
                a[i] = -1; 
                if (&a[i] != &a[checkIdx]) 
                { 
                    lBuff1.Set(&a[i]); 
                } 
            } 
            NodeBuf.push_back(lBuff1); 
 
            for (int i = 0; i < BUFSIZE; i++) 
            { 
                a[i] = -1; 
                if (&a[i] != &a[checkIdx]) 
                { 
                    lBuff1.Set(&a[i]); 
                } 
            } 
            NodeBuf.push_back(lBuff2); 
 
            int idxflag = 0; 
            int idx; 
            for (int i = 0; i < 3; i++) 
            { 
                Buff Bf; 
                idxflag = i % 2; 
                printf("Node Number %d\n", idxflag); 
                getchar(); 
                for (int k = 0; k < 10; k++) 
                { 
                    NodeBuf[idxflag].SetUnion(k); 
                } 
 
                NodeBuf[idxflag].Clear(); 
 
                checkIdx = NodeBuf[idxflag].TmpIdx(); 
                if (i > 0) 
                { 
                    int another = idxflag?0:1;  
 
                    printf("RESULT : %d : %d\n", *NodeBuf[idxflag].GetSumResult(), *NodeBuf[another].GetSumResult() ); 
                    NodeBuf[idxflag].SetUnion(*NodeBuf[another].GetSumResult()); 
                    printf("Current Result : %d\n", *NodeBuf[idxflag].GetSumResult()); 
                    getchar(); 
                } 
 
                for (int k = 0; k < BUFSIZE; k++) 
                { 
                    if (&a[k] != NodeBuf[idxflag].GetSumResult()) 
                    { 
                        a[k] = -1; 
                        Bf.Set(&a[k]); 
                    } 
                } 
                NodeBuf[idxflag?0:1] = Bf; 
 
                //printf("Current Result : %d\n", *NodeBuf[idxflag].GetSumResult()); 
                getchar(); 
            } 
        } 
}; 
 
int main(int argc, char **argv) 
{ 
    BufManager *MyBuff;  
    MyBuff = new BufManager(); 
    MyBuff->Run(); 
} 
 

결론

버퍼풀을 이용한 merged sort는 유연하게 확장가능하다는 장점이 있다. 검색엔진을 예로 들자면, 어절이 분리될 경우, 2개 이상의 트리를 가지게 될건데, 이렇게 다수의 트리를 가지는 데이터들을 merged sort 하길 원한다면, 5개의 버퍼를 가지는 풀을 유지하면 될 것이다.

관련글

• 일반 Merged Sort