합병정렬

쪼개고 쪼개고 쪼개서 더이상 쪼갤 수 없을 만큼 쪼개고,

그 조각들을 순서대로 대소를 비교하며 채워넣고 반환하는 것을 반복하는 

전형적인 분할정복 문제이다.

import sys

sys.stdin = open("input.txt","r")

#func lines start

def mergeSort(arr):

length = len(arr)

if( length == 1 ):

return arr

else:

arr1 = mergeSort(arr[:int(length/2)])

arr2 = mergeSort(arr[int(length/2):] )

arr3 = []

arr3_adder = arr3.append

arr1_cursor = 0

arr2_cursor = 0

#대소 비교하며 채워넣기

while (arr1_cursor < len(arr1)) and (arr2_cursor < len(arr2)):

if( arr1[arr1_cursor] <= arr2[arr2_cursor]):

arr3_adder( arr1[arr1_cursor] )

arr1_cursor = arr1_cursor + 1

else:

arr3_adder( arr2[arr2_cursor] )

arr2_cursor = arr2_cursor + 1

#남은거 뒤에 붙여주기

if(arr1_cursor < len(arr1)):

arr3.extend(arr1[arr1_cursor:])

else:

arr3.extend(arr2[arr2_cursor:])

return arr3

#func line end

#main

if __name__ == "__main__":

arr = list(map(int, input().split()))

print( mergeSort(arr) )