데일리썽

1. 병합 정렬 (merge sort)

재귀용법을 활용한 정렬 알고리즘

리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

2. 구현

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

@Slf4j
public class MergeSort {
    public static void split(List<Integer> dataList) {
        int medium = (int)(dataList.size() / 2);
        List<Integer> leftList = dataList.subList(0, medium);
        List<Integer> rightList = dataList.subList(medium, dataList.size());
        log.error("________________ = {}", medium);
        log.error("________________ = {}", leftList);
        log.error("________________ = {}", rightList);
    }

    public static List<Integer> mergeSplit(List<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }

        int medium = (int)(dataList.size() / 2);
        List<Integer> leftList = mergeSplit(dataList.subList(0, medium));
        List<Integer> rightList = mergeSplit(dataList.subList(medium, dataList.size()));

        return merge(leftList, rightList);
    }
    public static List<Integer> merge(List<Integer> leftList, List<Integer> rightList) {
        int leftIndex = 0;
        int rightIndex = 0;

        List<Integer> mergedList = new ArrayList<>();

        // leftList, rightList 남아 있을 때
        while (leftList.size() > leftIndex && rightList.size() > rightIndex) {
            if (leftList.get(leftIndex) > rightList.get(rightIndex)) {
                mergedList.add(rightList.get(rightIndex));
                rightIndex++;
            } else {
                mergedList.add(leftList.get(leftIndex));
                leftIndex++;
            }
        }

        // leftList만 남아 있을 때
        while (leftList.size() > leftIndex) {
            mergedList.add(leftList.get(leftIndex));
            leftIndex++;
        }

        // rightList만 남아 있을 때
        while (rightList.size() > rightIndex) {
            mergedList.add(rightList.get(rightIndex));
            rightIndex++;
        }


        return mergedList;
    }

    public static void main(String[] args) throws Exception {
        Random rand = new Random();
        List<Integer> dataList = new ArrayList<>();
        for (int i = 0; i < 11; i++) {
            dataList.add(rand.nextInt(11));
        }

        log.error("________________ = {}", dataList);

        dataList = mergeSplit(dataList);

        log.error("________________ = {}", dataList);
    }
}

3. 분석

시간복잡도는 O(nlogn)