集計ソートMerge Sort

マージソートMerge Sort*は、セミソートを続行し、マージします。

連結ソートは、配列を連続的に半分に分け、左半分、右半分をそれぞれ並べ替えてマージするアルゴリズムです.(分割後征服)
一時的に貯蔵するためには、異なる配列が必要です.

円アレイA、仮アレイB
連結ソートは、「前のステップ」(Top Down)で実行されます.
TopDown方式はWinsoを配列するまで割る方法です.

public class Main
{
    public static int[] arr2; // 임시 배열
    public static void merge(int[] arr, int start, int mid, int end)
    { // 반쪽 두개 병합. 각각은 정렬되어 있음
        arr2 = new int[end+1]; // 임시 배열의 크기는 원 배열과 같게
        int index = start; // 임시배열의 인덱스
        int i = start; // 왼쪽 배열의 시작
        int j = mid+1; // 오른쪽 배열의 시작
        while ((i <= mid) && (j <= end))
        {
            if (arr[i] <= arr[j])
            {
                arr2[index] = arr[i];
                i++;
            }
            else
            {
                arr2[index] = arr[j];
                j++;
            }
            index++;
        }
        
        if (i > mid) // 왼쪽 반 다 썼을 때
        {
            for (int k=j; k<= end; k++)
            {
                arr2[index] = arr[k];
                index++;
            }
        }
        
        else // 오른쪽 반 다 썼을 때
        {
            for (int k=i; k<= mid; k++)
            {
                arr2[index] = arr[k];
                index++;
            }
        }
        // 임시배열을 원 배열에 다시 넣음
        for (int k=start; k<=end; k++)
            arr[k] = arr2[k];
    }
    
    public static void mergeSort(int[] arr, int start, int end)
    { // 반쪽씩 정렬. 재귀 사용
        if (start < end)
        {
            int mid = (start + end)/2;
            mergeSort(arr, start, mid); // 왼쪽 반 정렬
            mergeSort(arr, mid+1, end); // 오른쪽 반 정렬
            merge(arr, start, mid, end); // 정렬 후 병합
        }
    }
    
    public static void printArr(int[] arr)
    {
        for (int i=0; i<arr.length; i++)
		    System.out.print(arr[i]+" ");
		 System.out.println();
    }
    
	public static void main(String[] args)
	{
	    int[] arr = {91, 82, 13, 85, 68, 70, 98, 24};
	    printArr(arr);
	    mergeSort(arr, 0, arr.length-1);
	    printArr(arr);
	}
}

時間的複雑度はO(Nlogn)である.分裂配列の過程で8−>4−>2−>1式が分裂するので,その高さはO(logn)である.各フェーズのマージでは、すべての値を比較する必要があるため、O(N)の時間が必要になります.
Boottom Up方式は1つ,2つ,4つの繰り返しソート方法である.各要素は配列された配列であると考えられます.
実施すると、以下のように-mergeは同じで、mergeSortのみ変更します.

public static void mergeSort(int[] arr, int end)
{
    int size = 1; // size는 1,2,4,8,16... 반쪽 씩 합쳐지면서 두배로 커짐
    while (size <= end)
    {
        for (int i=0; i<=end-size; i=i+2*size)
        {
            int high = Math.min(i+2*size-1, end);
            merge(arr, i, i+size-1, high);
        }
        size*=2;
    }
}

public static void main(String[] args)
{
    int[] arr = {91, 85, 68, 70, 98, 24, 1,2,3,4,9};
    printArr(arr);
    mergeSort(arr, arr.length-1);
    printArr(arr);
}

同様に,時間的複雑度はO(Nlogn)である.
マージソートには入力サイズと同じ仮配列が必要であるため,空間複雑度はO(N)である.
分割征服を用いてO(nlogn)の時間において所与の配列から重複を除去する場合,Merge Sortを用いて解決できる.
基本的なMerge SortのMergeメソッドは次のとおりです.

while ((i <= mid) && (j <= end))
{
    if (arr[i] <= arr[j])
    { // 왼쪽 반의 원소가 더 작거나 같다면 왼쪽 원소를 arr2에 넣음
        arr2[index] = arr[i];
        i++;
    }
    else
    { // 오른쪽 반의 원소가 더 작다면 오른쪽 원소를 arr2에 넣음
        arr2[index] = arr[j];
        j++;
    }
    index++;
}

次のように変更します.

while ((i <= mid) && (j <= end))
{
    if (arr[i] < arr[j])
    { // 왼쪽 반의 원소가 더 작다면 왼쪽 원소를 arr2에 넣음
        arr2[index] = arr[i];
        i++;
    }
    else if (arr[i] > arr[j])
    { // 오른쪽 반의 원소가 더 작다면 오른쪽 원소를 arr2에 넣음
        arr2[index] = arr[j];
        j++;
    }
    else // 양쪽 원소가 같을 때
    { // arr2에 원소 넣지 않고 한쪽 인덱스만 증가시킴
    	i++; // j++ 해도 됨.
    }
    index++;
}