Merge Sort - 병합 정렬

합병 정렬 또는 병합 정렬이라고 합니다.

재귀호출로 길이가 1인 배열로 분리시키고 분리된 배열을 비교해 순서를 바꿔주며 병합합니다.

 

https://en.wikipedia.org/wiki/Merge_sort

Merge sort - Wikipedia

Go로 구현한 코드입니다.

package main

import "fmt"

// 재귀호출로 길이가 1인 배열로 분할된 두 배열을 병합합니다.
func Merge(left, right []int) []int {

	result := make([]int, 0, len(left)+len(right))
	fmt.Println(left, right)

	for len(left) > 0 || len(right) > 0 {

		if len(left) == 0 {
			return append(result, right...)
		}

		if len(right) == 0 {
			return append(result, left...)
		}

		if left[0] < right[0] {
			result = append(result, left[0])
			left = left[1:]
		} else {
			result = append(result, right[0])
			right = right[1:]
		}
	}

	return result
}

// 병합정렬(Merge sort)를 수행합니다.
func MergeSort(arr []int) []int {

	if len(arr) <= 1 {
		return arr
	}

	middle := len(arr) / 2

	left := MergeSort(arr[:middle])
	right := MergeSort(arr[middle:])

	return Merge(left, right)
}

func main() {
	arr := []int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
	fmt.Println("Initial array is:", arr)
	fmt.Println("")
	fmt.Println("Sorted array:    ", MergeSort(arr))
}

각 코드에 대한 주석을 달았습니다.

package main

import "fmt"

// 재귀호출로 길이가 1인 배열로 분할된 두 배열을 병합합니다.
func Merge(left, right []int) []int {

	// int를 담을 수 있는 slice를 만듭니다.
	// length는 0이고 capacity는 left와 right의 길이를 합한 용량입니다.
	result := make([]int, 0, len(left)+len(right))
	fmt.Println(left, right)

	// left의 길이가 0보다 크거나 또는 right의 길이가 0보다 크다면 Loop를 진행합니다.
	// 즉 left건 right건 둘 중 하나의 길이가 0이 될때까지 돌려줍니다.
	for len(left) > 0 || len(right) > 0 {

		// left의 길이가 0이라면 right를 result에 담습니다. 
		// 병합(merge)가 완료되어 left는 0이되었고 나머지인 right를 result에 담는 것입니다.
		// result에 담길(merge 되는) right는 길이가 1이상일 수 있으니 ellipsis(...)로 표현합니다.
		if len(left) == 0 {
			return append(result, right...)
		}

		// 마찬가지로 right의 길이가 0이라면 left를 result에 담습니다.
		// 이번에는 병합(merge)가 완료되어 right가 0이되었고 나머지인 left를 result에 담는 것입니다.
		if len(right) == 0 {
			return append(result, left...)
		}

		// 만약 left와 right의 첫번째 자리를 비교해 right가 크다면
		if left[0] < right[0] {
			// left의 첫번째 자리를 result에 담습니다.
			result = append(result, left[0])
			// 그리고 첫번째 자리를 뺀 left를 다시 left에 담습니다.
			left = left[1:]
			// 만약 left와 right의 첫번째 자리를 비교해 left가 크다면
		} else {
			// right의 첫번째 자리를 result에 담습니다.
			result = append(result, right[0])
			// 그리고 첫번째 자리를 뺀 right를 다시 right에 담습니다.
			right = right[1:]
		}
	}

	// result를 반환합니다.
	return result
}

// 병합정렬(Merge sort)를 수행합니다.
func MergeSort(arr []int) []int {

	// 재귀함수(MergeSort)를 통해 길이가 1이거나 작을때 까지 돌립니다.
	// 재귀함수는 반드시 탈출 조건이 있어야 합니다.
	if len(arr) <= 1 {
		return arr
	}

	// 배열의 길이를 반으로 나눈 값을 할당합니다.
	middle := len(arr) / 2

	// 배열을 가운데 위치를 기준으로 left와 right로 나눕니다.
	// 재귀함수이므로 길이가 1보다 같거나 작을때까지 재귀호출을 계속 진행합니다.
	// 그럼 길이가 1이되는 배열로 분할됩니다.
	left := MergeSort(arr[:middle])
	right := MergeSort(arr[middle:])

	return Merge(left, right)
}

func main() {
	arr := []int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
	fmt.Println("Initial array is:", arr)
	fmt.Println("")
	fmt.Println("Sorted array:    ", MergeSort(arr))
}

재귀호출은 머리속에서 잘 그려지지 않는 경우가 있습니다.

그럴땐 그냥 그려보는게 좋습니다.

재귀호출로 길이가 1인 배열로 전부 나눠버립니다.

그리고 배열의 첫번째 자리를 비교해 순서대로 병합하며 정렬하는 방식입니다.

 

goroutine을 이용한 처리도 여럿 보이네요.

https://medium.com/@yliu224/goroutines-on-mergesort-12a2a7a43cc2

Goroutines on Mergesort

https://hackernoon.com/parallel-merge-sort-in-go-fe14c1bc006

Parallel Merge Sort in Go

병렬처리하는 것도 재밌어 보입니다.