4.병합 정렬

QuickSort 와 마찬가지로 Merge Sort는 Divide and Conquer 알고리즘입니다.

입력 배열을 두 개의 절반으로 나누고 두 개의 절반을 호출한 다음 정렬된 두 개의 절반을 병합합니다.

merge() 함수 는 두 개의 반쪽을 병합하는 데 사용됩니다.

merge(arr, l, m, r)는 arr[l..m]과 arr[m+1..r]이 정렬되어 있다고 가정하고 두 개의 정렬된 하위 배열을 하나로 병합하는 핵심 프로세스입니다.


병합 정렬(arr[], l, r)
r > l인 경우 
1. 배열을 두 개의 반으로 나눌 중간점을 찾습니다.
             중간 m = l+(rl)/2
2. 전반부에 대해 mergeSort를 호출합니다.
             mergeSort(arr, l, m) 호출
3. 후반부에 mergeSort를 호출합니다.
             mergeSort(arr, m+1, r) 호출
4. 2단계와 3단계에서 정렬된 두 개의 반쪽을 병합합니다.
             병합 호출(arr, l, m, r)

다음 다이어그램은 예시 배열 {38, 27, 43, 3, 9, 82, 10}에 대한 전체 병합 정렬 프로세스를 보여줍니다. 다이어그램을 자세히 살펴보면 배열이 크기가 1이 될 때까지 두 개의 반으로 재귀적으로 분할된 것을 볼 수 있습니다. 크기가 1이 되면 병합 프로세스가 작동하고 완전한 배열이 될 때까지 배열을 다시 병합하기 시작합니다.


// JavaScript program for Merge Sort
 
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
function merge(arr, l, m, r)
{
    var n1 = m - l + 1;
    var n2 = r - m;
 
    // Create temp arrays
    var L = new Array(n1);
    var R = new Array(n2);
 
    // Copy data to temp arrays L[] and R[]
    for (var i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (var j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
 
    // Merge the temp arrays back into arr[l..r]
 
    // Initial index of first subarray
    var i = 0;
 
    // Initial index of second subarray
    var j = 0;
 
    // Initial index of merged subarray
    var k = l;
 
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    // Copy the remaining elements of
    // L[], if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    // Copy the remaining elements of
    // R[], if there are any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
 
// l is for left index and r is
// right index of the sub-array
// of arr to be sorted */
function mergeSort(arr,l, r){
    if(l>=r){
        return;//returns recursively
    }
    var m =l+ parseInt((r-l)/2);
    mergeSort(arr,l,m);
    mergeSort(arr,m+1,r);
    merge(arr,l,m,r);
}
 
// UTILITY FUNCTIONS
// Function to print an array
function printArray( A, size)
{
    for (var i = 0; i < size; i++)
       document.write(  A[i] + " ");
}
 
 
var arr = [ 12, 11, 13, 5, 6, 7 ];
    var arr_size = arr.length;
 
    document.write(  "Given array is <br>");
    printArray(arr, arr_size);
 
    mergeSort(arr, 0, arr_size - 1);
 
    document.write( "<br>Sorted array is <br>");
    printArray(arr, arr_size);
 
// This code is contributed by SoumikMondal