병합 정렬(Merge Sort)에 대해 알아보자!

병합 정렬

• 오름차순을 기준으로 정렬.
• 비교적 안정 정렬에 속하며, 분할 정복 알고리즘 중 하나.
  
  
• 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 봄.
• 정렬되지 않은 리스트를 낱개가 될 때까지 절반씩 반복적으로 두 부분 리스트로 나눔.
• 재귀함수를 통해 병합 정렬을 진행.

<이미지 출처: https://gmlwjd9405.github.io/images/algorithm-merge-sort/merge-sort-concepts.png>

---

병합 정렬 C# 코드

    public List<int> DivideArr(List<int> list)
    {
        if (list.Count <= 1)
            return list;

        List<int> leftList = new List<int>();
        List<int> rightList = new List<int>();

        for (int i = 0; i < list.Count; i++)
        {
            if (i < list.Count / 2)
            {
                leftList.Add(list[i]);
            }
            else
            {
                rightList.Add(list[i]);
            }
        }

        leftList = DivideArr(leftList);
        rightList = DivideArr(rightList);

        return Merge_Sort(leftList, rightList);
    }
    
    public List<int> Merge_Sort(List<int> leftList, List<int> rightList)
    {
        List<int> mergedList = new List<int>();
        int leftIndex = 0;
        int rightIndex = 0;
        while (leftList.Count > leftIndex && rightList.Count > rightIndex)
        {
            if (leftList[leftIndex] <= rightList[rightIndex])
            {
                mergedList.Add(leftList[leftIndex]);
                leftIndex++;
            }
            else
            {
                mergedList.Add(rightList[rightIndex]);
                rightIndex++;
            }
        }
        if (leftList.Count > leftIndex)
        {
            for (int i = leftIndex; i < leftList.Count; i++)
            {
                mergedList.Add(leftList[i]);
            }
        }
        else if (rightList.Count > rightIndex)
        {
            for (int i = rightIndex; i < rightList.Count; i++)
            {
                mergedList.Add(rightList[i]);
            }
        }
        return mergedList;
    }

 

• 장점
  - 안정적인 정렬 방법. 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일함.
  
  
• 단점
  - 부분 리스트를 담을 임시 배열이 필요.
  - 배열의 크기가 큰 경우에는 이동 횟수가 많으므로 시간적 낭비 초래.

<이미지 출처: https://gmlwjd9405.github.io/images/algorithm-merge-sort/sort-time-complexity.png>

---