이미 정렬된 두 자료를 병합하는 것을 일반화 하여 정렬하는 알고리즘

자료 배열에 접근하는 방법이 순차적이어서 자료를 차례대로 읽어가며 비교를 하며

다른 메모리를 정렬에 이용한다.

1. 병합 병렬할 size = 1

2. size가 자료크기 N보다 작을 때 size의 크기로 배열을 분할하여 두 분할씩 차례로 병합

3. size = size * 2,   2번으로..

장점 : N logN의 성능을 가진다. 빠르다.

단점 : 추가적인 메모리로 정렬 할 배열과 똑같은 크기의 배열이 필요하다.

void Merge_Sort( int arr[], int len )

{

int i, j, k, first, second, size;

int *b;

b = (int*)malloc(sizeof(int)*len );

for( size = 1 ; size < len ; size *= 2 )

{

first =- 2*size;

second = first + size;

while( second + size*2 < len )

{

first = second + size;

second = first + size;

i = first;

j = second;

k = first;

while( i < first + size || ( j < second + size&& j < len ) )

{

if( arr[i] <= arr[j] )

{

if( i < first + size )

b[k++] = arr[i++];

else

b[k++] = arr[j++];

}

else

{

if( j < second + size && j < len )

b[k++] = arr[j++];

else

b[k++] = arr[i++];

}

}

}

for( i = 0 ; i < len ; i++ )

arr[i] = b[i];

}

free(b);

}