[알고리즘/자료구조] 분할 합병 정렬(Merge Sort)

분할 합병 정렬(Merge Sort)

합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다.

소스

/*
/*    
/*    khsh5592@naver.com
/*    has3ong.tistory.com
/*    
/*    2018 - 11 - 16
/*
*/
 
#include <iostream>
#include <stdio.h>
#include <conio.h>
 
using namespace std;
 
int Data[16] = {9, 19, 62, 5, 55, 33, 12, 23, 4, 123, 85, 1, 18, 6, 3, 11};
int Copy_Data[16];
 
 
void print()
{
    cout << " Data Array is [ " ;
    for (int i = 0; i < 16; i++)
    {
        cout << Data[i] << " ";
    }
    cout << "] "<< endl;
}
void TopDownMerge(int A[], int left, int middle, int right, int B[])
{
    int i = left;
    int j = middle;
 
    for(int k = left; k < right; k++)
    {
        if( i < middle && ( j >= right || A[i] <= A[j]))
        {
            B[k] = A[i];
            i++;
        }
        else
        {
            B[k] = A[j];
            j++;
        }
    }
    print();
}
 
void TopDownSplitMerge(int B[], int left, int right, int A[])
{
    if(right - left < 2)
    {
        return;
    }
 
    int middle = (left+right) / 2;
 
    TopDownSplitMerge(A, left, middle, B);
    TopDownSplitMerge(A, middle, right, B);
 
    TopDownMerge(B, left, middle, right, A);
}
 
void CopyArray(int A[], int left, int right, int B[])
{
    for(int k = left; k< right; k++)
    {
        B[k] = A[k];
    }
}
 
void TopDownMergeSort(int A[],int B[],int n)
{
    CopyArray(A,0,n,B);
    TopDownSplitMerge(B,0,n,A);
}
 
 
void main()
{
    int length = sizeof(Copy_Data) / sizeof(Copy_Data[0]);
    TopDownMergeSort(Data, Copy_Data, length);
 
    getch();
 
}

출처

위키피디아

https://en.wikipedia.org/wiki/Merge_sort