Merge Sort

Merge sort는 주어진 element array를 나눈뒤 합치면서 정렬하는 방법이다.

 

time complexity는 O(nlogn)이다.

 

stable한 성질을 가지고있다.

 

 

# Title : Merge Sort
# Chapter : Sorting
# 문제: 주어진 array를 Merge sort 하여라

from typing import List

def mergeSort(nums:List[int]) -> List[int]:
    # split
    length = len(nums)
    if length == 1:
        return nums

    mid = length // 2

    left_nums = nums[:mid]
    right_nums = nums[mid:]

    sorted_left = mergeSort(left_nums)
    sorted_right = mergeSort(right_nums)

    # merge, Swap approach is memory friendly. But..
    # For the easy code, new array sorted_nums is created
    sorted_nums = []
    idx_l = 0
    idx_r = 0
    while idx_l < len(sorted_left) or idx_r < len(sorted_right):
        if idx_l == len(sorted_left):
            sorted_nums.append(sorted_right[idx_r])
            idx_r += 1
            continue
        
        if idx_r == len(sorted_right):
            sorted_nums.append(sorted_left[idx_l])
            idx_l += 1
            continue
        
        if sorted_left[idx_l] <= sorted_right[idx_r]:
            sorted_nums.append(sorted_left[idx_l])
            idx_l += 1
        else:
            sorted_nums.append(sorted_right[idx_r])
            idx_r += 1

    return sorted_nums


print(mergeSort(nums=[5,7,9,3,1,2,4]))

 

참조 : (2) 코딩테스트, 초급, 병합정렬, Merge Sort - YouTube