🌐What is MergeSort?

 여기 두개의 카드 팩이 있습니다. 먼저 머릿속으로 이 두개의 카드팩을 합쳐서 오름차순으로 숫자들을 정렬해봅시다.

 다 해보셨나요?

 그럼 이번엔 아래의 카드팩을 오름차순으로 정렬해봅시다.

 어떤가요? 카드의 갯수가 적어서 시간적인 차이는 느껴지지 않을 수도 있지만,
"정렬하기 어느쪽이 더 편한가요?"
라고 물어본다면 바로 떠오르는 카드팩이 있을 것입니다.
(천재이신 분은 죄송하지만 논외로 하겠습니다)

  여러분들은 방금 MergeSort의 Merge 과정을 직접 해보셨습니다👏
이미 각각의 카드팩이 정렬이 되어있으니 단지 각각의 카드팩의 맨앞에서부터 하나씩 뽑아 서로 비교하며 순서대로 나열만 해주면 정렬이 완료되겠죠!

🌐MergeSort Process

위의 카드 정렬이 간단한 예시였지만 사실 MergeSort의 모든 과정을 캐치할 수 있는 중요한 예시입니다.

📔주요진행과정

1. 정렬이 필요한 배열을 절반씩 두 개의 배열로 나눈다.
2. 두 개로 나뉘어진 배열을 각각 정렬한다.
3. 정렬된 두 개의 배열을 합친다. (Merge)

그런데, 눈치채셨겠지만 정렬과정인데 그 안에 또 정렬과정이 들어갑니다. 지금 떠오르는 단어 있지 않나요? '재귀' 라는 단어가 떠오릅니다. 즉, 정렬 안에 정렬이 있다고 해서 복잡하게 생각할 것이 아니라,
"내가 만들어 놓은 process를 그냥 반복해서 이용하자!"
라고 생각하신다면 마음이 한결 놓일 것입니다.

📔언제까지 이 과정을 반복할까?

간단합니다.

"이거 둘 자리 바꾸기만 하면 되는거 아니야?" "한 개는 좀..."

나누고 나눠 배열의 숫자가 1개 또는 2개가 된다면 더 이상 위의 프로세스를 진행할 필요가 없습니다. 순서가 맞지 않으면 바꿔주고, 1개라면 그냥 놔두면 되니까요.

📔진행과정을 한눈에!

위에서 살펴봤던 MergeSort의 진행과정은 알고리즘 중 하나인 Divide-and-Conquer (분할정복)의 대표적인 예시입니다. 따라서 분할정복 알고리즘의 진행과정에 따라 3가지 단계로 MergeSort의 과정을 다이어그램으로 보겠습니다.

1. Divide & Conquer

2. Escape Recursion (재귀 탈출)

3. Conquer & Combine (= Merge)

🏆마치며..

이번 포스팅에서 제가 공부한 내용을 바탕으로 MergeSort의 과정에 대해 작성해보았습니다. 독자분들, 특히 처음 MergeSort를 보시는 분께 최대한 직관적으로 이해하실 수 있게 써보았는데 글솜씨가 없어서 잘 읽히실지 모르겠습니다. 잘 이해가 안되는 부분에 대해서는 댓글 남겨주세요! 그리고 틀린부분이나 오타 등 피드백은 항상 감사히 받겠습니다.😄
다음 포스팅은 코드와 함께 MergeSort의 시간,공간 복잡도, 정렬의 종류에 대해 정리해보겠습니다.📊🖋👊