Merge Sort 알고리즘

Merge Sort 알고리즘은 주어진 배열/리스트를 분할해서 각각 정렬하고 그를 다시 합병하여 정렬을 해 진행해 나가는 구조의 정렬 알고리즘이다.

만약 리스트/배열의 길이가 0이나 1이라면 이미 정렬된 것으로 치부한다.
그렇지 않은 경우에는 리스트/배열을 절반으로 잘라 비슷한 크기를 가진 부분 리스트/배열로 나누고 합병 정렬을 한다.
마지막에는 이 두개의 부분 리스트/배열을 하나의 정렬되었는 리스트/배열로써 합병한다.

이 그려진 도표를 보게 되면

위의 도표는 이미 분할이 되었는 상태에서 다시 병합하는 과정을 역순으로 그린 도표인데 실제로 Merge Sort가 진행되는 과정을 나타내자면

이런과정으로 진행된다.
이제 이를 일반적인 방법으로 구현을 하게 된다면 리스트의 시작과 끝을 기준으로 mid 값을 찾고 그 값을 기준으로 리스트/배열을 분할하게 될 것이다.

그리고 정렬되었는 리스트/배열만이 남게된다면 두개의 부분 리스트/배열을 합병하게 되는데 합병을 할때에는 두개의 리스트/배열에서 첫번째 값을 서로 비교하고 더 작은 값을 새로운 리스트/배열에 넣는 과정을 수행할 수 있을것이다.

이러한 과정을 되풀이하며 두 리스트/배열 중 하나가 먼저 끝나게 되면 나머지 리스트/배열의 값을 새로운 리스트/배열로 옮기면 합병과정을 수행한 것이 되는 것이다.