1. 정렬

정렬(Sorting)은 데이터를 사용자가 설정한 기준에 따라서 순서대로 나열하는 것을 말한다. 보통은 문제의 조건에 따라서 오름차순이나 내림차순으로 정렬을 한다. 정렬되는 데이터는 꼭 하나의 '수' 혹은 '문자' 뿐만 아니라, 데이터 값이 2개가 입력된 튜플 자료형이 하나의 값으로써 사용자의 설정에 따라서 정렬되기도 한다. 단순히 정렬을 해야 하는 경우라면 내장 함수 sort, sorted를 사용하는데, 문제의 조건에 따라서 직접 정렬을 시켜야 하는 경우도 있기에 여러가지 방법으로 데이터를 정렬하는 법을 살펴보자.
특히 선택, 삽입, 버블, 계수정렬은 for/while 반복문을 통해 정렬을 시키는데 반해, 병합정렬과 퀵정렬은 재귀함수를 통한 반복문을 실행시키기에 앞의 4가지 방법보다 연산이 빠르다는 장점이 있지만 재귀함수의 이해가 선행되지 않으면 이해하기 조금 어렵다는 단점이 있다 병합과 퀵정렬을 살펴보겠다.

2. 병합정렬

병합정렬은 입력된 데이터를 분할하고 각각의 분할된 자료를 정렬한 후 다시 병합하면서 정렬하는 것을 말한다.우선 위의 그림과 같이 먼저 분할하는 단계를 거친 뒤, 아래의 그림처럼 정렬하면서 병합하는 단계를 거친다. 문제를 작은 단위로 분할하여 각각 해결한 뒤, 그 결과를 합쳐 원래의 문제를 해결하는 전략으로, 이렇게 분할하여 정복한다고 해서 붙여진 이름이 분할정복(Divide & conquer) 방법이다. 분할한 뒤 합치는 연산이 일어나기에 후위순회 방식으로 진행된다.
그림출처:제로베이스

2.1 과정

1. 파이썬에서는 병합정렬을 위해 리스트를 사용한다. 먼저 입력된 리스트를 두 개의 균등한 리스트로 나눈다. 리스트를 2분할로 나누기 위해서 재귀함수를 사용하는데, 반을 중심으로 해서 '처음부터 중간 전 인덱스', '중간부터 마지막'으로 나눈다. 이렇게 나누어진 리스트는 다시 재귀적으로 길이가 1일 때까지 분할한다.
2. 길이가 1이면 그 자체로 정렬된 것이므로, 함수를 종료시켜서 작은 부분으로 나눠진 리스트를 재귀적으로 다시 합병해 나간다.
3. 합병할 때 나누어진 두 개의 리스트는 길이가 1이기에 이미 정렬되어 있어서, 두 개의 리스트를 인덱스 0부터 비교하여 둘 중 값이 낮은 순으로 새로운 임시 리스트에 합쳐진다. 이렇게 합쳐질 때 한쪽의 리스트가 비게 되면 나머지 리스트의 순서에 따라서 합쳐진다. 점진적으로 이미 1부터 시작해서 낮은 값부터 병합되기에 리스트는 오름차순으로 정렬되어 있음이 전제되어 있다.

2.2 코드

def Msort(lt, rt): # 정렬되지 않은 리스트의 처음과 끝의 인덱스를 매개변수로 받는다
    if lt < rt: # 리스트의 길이가 1이 될 때까지 분할(길이가 1이라면 lt == rt)
        mid = (lt + rt) // 2
        Msort(lt, mid) # 처음부터 중간까지
        Msort(mid+1, rt) # 중간 다음부터 끝까지 나누기
        # 길이가 1이 되면 후위순회
        lp = lt # 한 쪽의 시작 인덱스
        rp = mid + 1 # 다른 한 쪽의 시작 인덱스
        tmp = [] # 두 개의 리스트를 병합할 임시 변수
        while lp <= mid and rp <= rt: # 한 쪽의 리스트가 빌 때 까지, 값이 작은 순으로 병합
            if arr[lp] < arr[rp]:
                tmp.append(arr[lp])
                lp += 1
            else:
                tmp.append(arr[rp])
                rp += 1
         # 아직 합쳐지지 않은 리스트 병합하기
        if lp <= mid:
            tmp += arr[lp:mid+1]
        if rp <= rt:
            tmp += arr[rp:rt+1]
        # 정렬되지 않은 본래의 리스트에 임시변수 덮어씌우기
        for i in range(len(tmp)):
            arr[lt+i] = tmp[i]
if __name__ == '__main__':
    arr = [8, 1, 4, 3, 2, 5, 10, 6]
    lt = 0
    rt = len(arr) - 1
    print(Msort(lt, rt))

3. 복잡도

분할단계에서는 이분검색처럼 반씩 줄여가며 분할이 되기에 O(logN)의 연산 횟수만큼, 그리고 합병은 모든 수를 비교하여 합차기에 각각으로 O(N)으로 병합정렬의 시간복잡도는 O(NlogN)으로 앞선 삽입, 선택, 버블, 계수정렬(O(N**2))보다 빠른 연산이 가능하다.