Python - 병합정렬

병합정렬

 병합정렬은 저장된 데이터를 각각 끝까지 쪼갠 후 쪼갠 상태에서 병합하면서 정렬하는 방식이다.

 

예제

def mSort(ns, asc=True):
    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    leftNums = mSort(ns[0:midIdx], asc=asc)
    rightNums = mSort(ns[midIdx:len(ns)], asc=asc)

    mergeNums = []

    leftIdx = 0
    rightIdx = 0

    while leftIdx < len(leftNums) and rightIdx < len(rightNums):

        if asc:
            if leftNums[leftIdx] < rightNums[rightIdx]:
                mergeNums.append(leftNums[leftIdx])
                leftIdx += 1

            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1
        else:
            if leftNums[leftIdx] > rightNums[rightIdx]:
                mergeNums.append(leftNums[leftIdx])
                leftIdx += 1

            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1

    mergeNums = mergeNums + leftNums[leftIdx:]
    mergeNums = mergeNums + rightNums[rightIdx:]

    return mergeNums

import random as rd

rNums = rd.sample(range(1, 101), 10)
print(rNums)
print(mSort(rNums))
print(mSort(rNums, asc=False))

내용

재귀함수를 이용하여 구현한다.

 데이터의 길이가 1이 될때까지 나누고 각각 나눈 데이터를 비교하여 오름차순, 내림차순에 맞게 새 리스트에 정렬된 값을 넣어주고 리턴한다.

재귀함수로 반복해서 분할된 데이터들은 리턴하면서 정렬하여 마지막엔 전체 데이터가 정렬된 리스트를 만든다

 

결과

[6, 37, 23, 18, 71, 1, 84, 38, 76, 41]
[1, 6, 18, 23, 37, 38, 41, 71, 76, 84]
[84, 76, 71, 41, 38, 37, 23, 18, 6, 1]