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

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

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

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);

}

이미 정렬된 자료인 경우 : 삽입, 거품, 퀵

자료가 섞여 있는 경우 : NlogN의 성능을 가지는 정렬방법들

반쯤 정렬된 경우 : 퀵, 쉘, 병합

역순으로 정렬된 자료 : 개선된 퀵, 쉘, 병합, 힙(최악 : 선택,삽입,거품)

추가적인 메모리 소요가 필요한 정렬 : 기수, 병합

우선순위 큐의 일종으로 우선 순위가 높은 요소를 효율적으로 선택 할 수 있는 자료구조.

힙을 트리를 이용하여 구현하며 트리는 배열로 구현.

힙 : 우선순위가 키 값의 크기에 정해지는 우선순위 큐. 어떤 키가 다른 특정한 두 키보다 큰 값을

가져야 한다는 조건이 만족해야 함( 트리구조 )

Upheap : 새로 삽입된 노드가 힙의 규칙에 맞게 지위가 상승하는 작동

Downheap : 힙의 상단을 차지하던 노드가 힙의 규칙에 맞게 지위에 떨어뜨리는 동작

힙 삽입, 추출시 위 동작들을 이용하여 힙을 완성 시킨다.