[알고리즘] 병합정렬(Merge sort)

---

이전 포스팅에서 분할 정복에는 병합 정렬과 퀵 정렬이 있다 언급했었는데요, 오늘은 병합 정렬에 대해 공부해봅니다.

https://geukggom.tistory.com/169

 

---

1. 병합 정렬이란?

: 분할 정복 방식의 알고리즘이며, 재귀용법을 이용한 정렬 알고리즘입니다.

 

병합정렬의 방식을 단계별로 설명하면 다음과 같습니다.

1) 배열을 반으로 쪼갭니다.

2) 1) 과정을 재귀용법을 이용해 반복합니다.

3) 쪼개진 두 배열들을 합병 정렬을 이용해 합치며 정렬합니다.

 

움짤로 보시면 더 이해가 쉽습니다.

출처 : https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

 

 

---

2. 병합 정렬 구현

위에서 설명한 단계별로 구현해보겠습니다.

 

1) 배열을 반으로 쪼갭니다.

int cutNum = list.Count / 2;

List<int> leftList = list.ToList();
List<int> rightList = list.ToList();

leftList.RemoveRange(cutNum, list.Count - cutNum);
rightList.RemoveRange(0, cutNum);

 

2) 1) 과정을 재귀용법을 이용해 반복합니다.

public List<int> mergeSort(List<int> list)
{
    if (list.Count <= 1) return list;
    int cutNum = list.Count / 2;

    List<int> leftList = list.ToList();
    List<int> rightList = list.ToList();

    leftList.RemoveRange(cutNum, list.Count - cutNum);
    leftList = mergeSort(leftList);

    rightList.RemoveRange(0, cutNum);
    rightList = mergeSort(rightList);

    return mergeList(leftList, rightList);
}

 

3) 쪼개진 두 배열들을 합병 정렬을 이용해 합치며 정렬합니다.

public List<int> mergeList(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;
}

---

GitHub