병합 정렬(Merge Sort)

//병합 정렬

//*Array : 정렬할 데이터 배열, Start : 데이터 시작위치, End : 데이터 마지막 위치

void Sort::MergeSort(int * Array, int Start, int End)

{

        //분할된 그룹의 크기가 1이하면 수행안함

        if (End <= Start)

               return;

 

        int mid = (Start + End) / 2;      //중간 데이터의 위치

        int length = End - Start + 1;     //분할된 그룹의 크기

        int *copyArray = new int[length]; //임시 저장공간

 

        int first = Start;    //첫번째 그룹의 시작 지점

        int second = mid + 1; //두번째 그룹의 시작 지점

        int copy = 0;         //임시 저장공간 인덱스

 

        //분할

        MergeSort(Array, Start, mid);    //첫번째 그룹

        MergeSort(Array, mid + 1, End);  //두번째 그룹

 

        //분할한 두 그룹을 다시 병합

        while (first <= mid && second <= End)

        {

               //임시 저장공간에, 데이터가 작은 순서대로 입력

               copyArray[copy++] =

                       Array[first] < Array[second] ? //첫번째 그룹의 데이터가 두번째 그룹의 데이터 보다 작은가?

                       Array[first++] :               //작다면 첫번째 그룹의 데이터 입력

                       Array[second++];               //아니라면 두번째 그룹의 데이터 입력

        }

       

        //입력이 되지 않고 남아 있는 데이터 처리

        //      어떤 그룹의 데이터가 남았는지 찾고

        int i = first <= mid ? first : second;

 

        //      순서대로 임시저장 공간에 입력

        for (; copy < length; copy++, i++)

               copyArray[copy] = Array[i];

 

        //데이터 목록에 임시저장한 데이터들 입력

        for (i = Start, copy = 0; i <= End; i++, copy++)

               Array[i] = copyArray[copy];

 

        //입시저장공간 메모리 해제

        delete[] copyArray;

        copyArray = NULL;

}