단일 쓰레드 병합 정렬(Merge sorting)

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>

#include <time.h>

#include <sys/time.h>

#define CHECK_END -1

static int *array = NULL;

static void div_array(int *, int, int);

static void merge_sort(int *);

static void init_array(int size)

{

int count = 0;

array = (int*)malloc(sizeof(int) * size);

for(count = 0 ; count < size ; count ++)

{

array[count] = rand()%size + 1;

}

}

static void display_array(int size)

{

int count = 0;

for(count = 0 ; count < size ; count ++)

{

printf("%d", array[count]);

if(count + 1 < size)

printf(", ");

else

printf(" END\n");

}

}

static void merge(int *arr, int start, int middle, int end)

{

int *arr_left, *arr_right;

int left = 0, right = 0;

int count = 0;

arr_left = (int*)malloc(sizeof(int) * (middle - start + 2));

arr_right = (int*)malloc(sizeof(int) * (end - middle + 1));

for(count = 0 ; count <= middle - start ; count ++)

{

arr_left[count] = arr[start + count];

}

arr_left[count] = CHECK_END;

for(count = 0 ; count < end - middle ; count ++)

{

arr_right[count] = arr[middle + count + 1];

}

arr_right[count] = CHECK_END;

for(count = start ; count <= end ; count ++)

{

if((arr_left[left] == CHECK_END || arr_left[left] > arr_right[right])

&& arr_right[right] != CHECK_END)

{

arr[count] = arr_right[right ++];

}

else

arr[count] = arr_left[left ++]; 

}

free(arr_left);

free(arr_right);

}

static void div_array(int *arr, int start, int end)

{

int middle = (start + end) / 2;

if(start < end)

{

div_array(arr, start, middle);

div_array(arr, middle+1, end);

merge(arr, start, middle, end);

}

}

int main(void)

{

srand(time(0));

struct timeval btime, atime;

long sec, msec;

int size = 0;

printf("input size of array : ");

scanf("%d", &size);

init_array(size);

// printf("before sorting\n");

// display_array(size);

gettimeofday(&btime, NULL);

div_array(array, 0, size-1);

gettimeofday(&atime, NULL);

sec = atime.tv_sec - btime.tv_sec;

msec = (sec * 1000) + ((atime.tv_usec - btime.tv_usec) / 1000);

// printf("after sorting\n");

// display_array(size);

printf("finished! %ldmsec.\n", msec);

return 0;

}