Merge sort(병합 정렬)

Merge sort(병합 정렬)

원칙1: 2개가 될때까지 쪼갠다.

원칙2: 2개가 되면 서로 비교해서 자리를 바꾸거나 바꾸지 않는다.

원칙3: 이렇게 조각난 2개를 4개로, 4개를 8개로... 순서를 맞추어 병합한다.

Best case: O(n) 

Average case: O()

Worst case: O() : 

# 재귀함수로 구현한 Merge sort

public class MergeSort implements ISort {

    @Override

    public void sort(Comparable[] array) {

        mergeSort(array, 0, array.length - 1);

    }

    private void mergeSort(Comparable[] array, int startIndex, int endIndex) {

        if (endIndex - startIndex < 1) {

            return;

        }

        int middleIndex = (endIndex + startIndex) / 2;

        mergeSort(array, startIndex, middleIndex);

        mergeSort(array, middleIndex + 1, endIndex);

        merge(array, startIndex, middleIndex, endIndex);

    }

    private void merge(Comparable[] array, int startIndex, int middleIndex, int endIndex) {

        Comparable[] mergedArray = new Comparable[endIndex - startIndex + 1];

        int indexA = startIndex;

        int indexB = middleIndex + 1;

        for (int i = 0; i < mergedArray.length; i++) {

            if (indexB > endIndex || (indexA <= middleIndex && array[indexA].compareTo(array[indexB]) < 0)) {

                mergedArray[i] = array[indexA++];

            } else {

                mergedArray[i] = array[indexB++];

            }

        }

        for (int i = 0, j = startIndex; i < mergedArray.length; i++, j++) {

            array[j] = mergedArray[i];

        }

    }

}

Reference:

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