병합 정렬merge sort

https://visualgo.net/en/sorting

재귀를 활용한 정렬 알고리즘
리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다
각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다
두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다

재귀함수와 배열을 사용해서 구현하였다..

public class MergeSort {

    private ArrayList<Integer> list;
    private ArrayList<Integer> buffer;

    MergeSort()
    {
        list = new ArrayList();
        buffer = new ArrayList();
    }

    void add(Integer value)
    {
        list.add(value);
    }

    void sort()
    {

        int start = 0;
        int end = list.size()-1;

        mergeSort(start, end, list, buffer);

    }

    void mergeSort(int start, int end, ArrayList<Integer> list, ArrayList<Integer> buffer)
    {
        if(end == start)
            return;

        int half = start + ((end - start) /2);

        mergeSort(start, half, list, buffer);
        mergeSort(half+1, end, list, buffer);

        int leftstart = start;
        int leftend = half;
        int rightstart = half + 1;
        int rightend = end;

        buffer.clear();
        while(true)
        {
            if(leftstart <= leftend && rightstart <= rightend)
            {
                if(list.get(leftstart) < list.get(rightstart))
                {
                    buffer.add(list.get(leftstart));
                    leftstart++;
                }
                else
                {
                    buffer.add(list.get(rightstart));
                    rightstart++;
                }
            }
            else if(leftstart <= leftend && rightstart > rightend)
            {
                buffer.add(list.get(leftstart));
                leftstart++;
            }
            else if(leftstart > leftend && rightstart <= rightend)
            {
                buffer.add(list.get(rightstart));
                rightstart++;
            }
            else
                break;
        }

        int idx = start;
        for(int i = 0; i < buffer.size(); ++i)
        {
            list.set(idx, buffer.get(i));
            idx++;
        }
    }

    @Override
    public String toString() {
        return list.toString();
    }
}

public class MergeSortTest {
    public static void main(String[] args) {

        MergeSort ms = new MergeSort();

        for(int i = 0; i < 20; ++i)
        {
            ms.add((int)(Math.random() * 100));
        }

        ms.sort();

        System.out.println(ms);
    }
}

병합정렬의 시간복잡도는 nlogn 이다
예를들어 8개의 원소가 있다고 하자.
알고리즘이 배열을 분할할때 3번순회해야한다(8개 원소들을 각각 1개씩 서로 떨어지도록 분할하는과정에 필요한 횟수. 8/2/2/2) 이것은 log8 의 값과 같다 즉 시간복잡도 logn 이된다
그리고 나눠진 8개의 원소들을 병합 하는 과정을 진행할때 8개를 다 돌면서 비교대조한뒤 병합해야 하므로 n 의 시간복잡도를 보인다
그렇므로 n x logn = nlogn 의 시간 복잡도를 가진다