merge sort

mergeSort(divide)

mergeSort(arr, l, r):
	if l<r:
    	m = (l+r)/2
    	mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)

merge(conquer)

merge(arr, l, m, r):
	i = l	# 왼쪽 배열의 인덱스 (l ~ m)
    j = m+1	# 오른쪽 배열의 인덱스 ("m+1" ~ r)
    idx = l
    
    while i<=m and j<=r:	# <=인 이유: i는 l~m까지 커버하고, j는 m+1~r까지 커버하기 때문!!
    	if arr[i]<arr[j]:
        	sorted[idx] = arr[i]
          	i++
        else:
        	sorted[idx] = arr[j]
        	j++
        idx++
    
    while i<=m:
    	sorted[idx] = arr[i]
        idx++
        i++
    while j<=r:
    	sorted[idx] = arr[j]
        idx++
        j++

merge sort가 뭔지, 어떤 원리인지는 이미 잘 안다.
그러나,
어떻게 코드를 구성하고 (어떻게 나누고, 합치는가?) 병합 시 부등호에서 등호의 존재 여부, j가 m+1인 이유 등 코딩으로 구현하는 노하우가 부족하다고 느꼈다. 자료구조와 알고리즘의 개념에 대한 이해 또한 무척 중요하지만, 배운 개념을 직접 코드로 구현하고 체화하지 못하면 의미가 없다고 느꼈다.