MergeSort

import java.util.Arrays;

public class MergeSort {
    public static void mergeSort(int arr[], int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    public static void merge(int arr[], int l, int mid, int r) {
        int i = l;
        int j = mid + 1;
        int temp_pos = l;
        int temp[] = new int[arr.length];
        while (i <= mid && j <= r) {
            if (arr[i] < arr[j]) {
                temp[temp_pos++] = arr[i++];
            } else {
                temp[temp_pos++] = arr[j++];
            }
        }
        while (i <= mid)
            temp[temp_pos++] = arr[i++];
        while (j <= r)
            temp[temp_pos++] = arr[j++];
        for (int index = l; index < temp_pos; index++)
            arr[index] = temp[index];
    }
}

import java.lang.reflect.Array;
import java.nio.channels.SeekableByteChannel;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SortMain {

    public static void main(String[] args) {

        int[] arr = SortUtil.makeTestArr(10);
        Arrays.stream(arr).forEach(value -> System.out.print(value + " "));
        System.out.println();
        Arrays.stream(arr).forEach(value -> System.out.print(value + " "));
    }
}

66 23 93 102 7 95 9 20 24 74 
7 9 20 23 24 66 74 93 95 102 

병합 정렬은 입력 목록의 사전 정렬에 영향을 받지 않는다.
퀵 정렬에서 대부분의 작업은 재귀 호출이 일어나기 전에 처리된다.
퀵 정렬은 큰 부파일에서 시작해서 작은 부파일로 끝난다. 따라서 스택이 필요하고 안정성을 가지지 않는 알고리즘이다. 반면 병합 정렬은 정렬할 목록을 두 개의 부분으로 나누고 두 부분을 따로 따로 정렬한다. 병합 정렬은 작은 부파일에서 시작하여 큰 부파일에서 끝난다. 따라서 스택이 필요없으며 안정성을 가진다.

병합 정렬은 정렬할 목록을 두 부분으로 나누고 재귀적으로 처리한다.
각 부분의 처리가 끝난 후 두 부분을 병합한다. n개의 요소를 병합 정렬하는 복잡도를 T(n)이라 하면 병합 정렬을 위한 반복은 다음과 같이 정의된다.

T(n) = 2*T(N/2) + O(n)
마스터 정리에 의해 T(n) = O(nlogn)

최악의 경우 복잡도 O(nlogn)
최선의 경우 복잡도 O(nlogn)