분할정복(Divide and Conquer)

#include <iostream>
#include <ctime>

#define SIZE 16

using namespace std;

template <class data>
void merge_sort(data *arr, int size);

int main()
{
        int arr[SIZE];
        srand(time(0));

        for(int i = 0 ; i < SIZE ; i++)
        {
               arr[i] = rand()%100 + 1;
               cout<<arr[i]<<" ";
        }

        merge_sort(arr, SIZE);
        cout<<endl<<endl;

        for(int i = 0 ; i < SIZE ; i++)
        {
               cout<<arr[i]<<" ";
        }
        return 0;
}

template <class data>
void merge_sort(data *arr, int size)
{
        if(size==1)
        {  
               return;
        }
 

        merge_sort(arr, size/2);
        merge_sort(arr+(size/2), size-(size/2));

        int tmp1[SIZE+1], tmp2[SIZE+1];
        int i;
        int l = 0, r = 0;

        for(i = 0 ; i < size/2 ; i++)
        {
                 tmp1[i] = arr[i];
        }

        tmp1[i] = INT_MAX;

        for(i = 0; i < size-(size/2) ; i++)
        {
                tmp2[i] = arr[i+(size/2)];
        }

        tmp2[i] = INT_MAX;

        for(i = 0 ; i < size ; i++)
        {
               if(tmp1[l] > tmp2[r])
               {
                      arr[i] = tmp2[r];
                      r++;
               }
               else
               {
                      arr[i] = tmp1[l];
                      l++;
               }
        }
}

main.cpp