[알고리즘 C언어] 4.3 병합 정렬(Merge Sort) 알고리즘

이번에는 병합 정렬 알고리즘을 살펴봅시다.

병합 정렬 알고리즘은 배열을 작은 단위의 배열로 분할한 후에 분할한 배열을 정렬하고 이들을 다시 정렬하면서 전체 배열을 정렬하는 알고리즘입니다.

병합 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

    ah:= n/2

    bh:= n – ah;

조건(n이 1보다 작거나 같으면) 종료

병합정렬(base,ah,compare)

병합접열(base+ah,bh,compare)

    tbase에 동적 메모리 할당(원소크기*원소개수)

메모리 복사(tbase,base)

    ai:=0

    bi:=ah

    i:=0

반복(ai가 ah보다 작으면서 bi가 n보다 작다)

조건(tbase[ai]가 tbase[bi]보다 작거나 같으면

            base[i] := base[ai]

            ai:= ai+1

아니면

             base[i]:= base[bi]

             bi:= bi+1

        i:=i+1

반복(ai가 ah보다 작다)

        base[i]:= tbase[ai]

        i:=i+1

        ai:=ai+1

반복(bi가 n보다 작다)

        base[i]:= tbase[bi]

        i:=i+1

        bi:=bi+1