합병 정렬이라고도 불리우며 분할 정복 방법을 통해 구현할 수 있습니다.
빠른 정렬로 분류되며 퀵소트와 함께 많이 언급되는 정렬 방식입니다.

요소를 쪼갠 후, 다시 병합시키면서 정렬해나가는 방식으로 쪼개는 방식은 퀵정렬과 유사합니다.

구현

재귀를 이용해서 병합 정렬을 구현할 수 있습니다. 먼저 배열을 더 이상 나눌 수 없을때까지 분할한 이후에 다시 병합하면서 점점 큰 배열을 만들어 나가면 됩니다. 따라서 이 재귀 알고리즘의 기저 조건은 입력 배열의 크기가 2보다 작을 때이며, 이 조건에 해당할 때는 배열을 그대로 반환하면 됩니다.

def merge_sort(arr):
	if len(arr) < 2:
    	return arr
        
    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])
    
    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
    	if low_arr[l] < high_arr[h]:
        	merged_arr.append(low[l])
            l += 1
        else:
        	merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low[l:]
    merged_arr += higharr[h:]
    return merged_arr 

임시 배열을 만들어서 사용하기 때문에 메모리적인 측면에서 비효율적인 코드여서 개선점을 생각해볼 수 있을 것 같습니다.