マージソート

• 「マージ」を操作として含む整列アルゴリズムのこと
• $O(n \log n)$の計算量
• 最悪の場合でも同じオーダーなので計算量の観点から安全と言えるが，整列させたい列と同程度のメモリが必要となるという欠点があり，この欠点が致命的である場面が多い
• マージソート中はデータに対して「順アクセス」することから，ランダムアクセス性のない二次記憶装置内でのデータの整列に用いられることがある

マージ

• 整列された複数の「列」を併せて，一つの整列された「列」を作る操作
• 整列された複数の列を統合して一つの整列された列を作り出す操作は簡単にできる
• 以下では二つの昇順に整列された列同士を統合して一つの昇順に整列された列を作り出すことにする
• それぞれの列から最小値を取り出して，その取り出された値同士を比較して小さい方から詰めていくことを繰り返せば「マージ」の操作は完了する
• 「列」を配列で表現したとするとこんな感じ

func Merge(arr1, arr2 []int) []int {
	m, n := len(arr1), len(arr2)
	i, j := 0, 0
	ret := make([]int, 0)
	for i < m && j < n {
		if arr1[i] <= arr2[j] {
			ret = append(ret, arr1[i])
			i++
		} else {
				ret = append(ret, arr2[j])
				j++
		}
	}
	if i < m {
		ret = append(ret, arr1[i:]...)
	}
	if j < n {
		ret = append(ret, arr2[j:]...)
	}
	return ret
}

単純マージソート

• 「マージ」という考え方をボトムアップに用いて列を整列させようとするアルゴリズムの一つ
• 「整列されている列同士をくっつけて一つの整列された列を作れんなら，それを繰り返せば整列アルゴリズムになるんじゃね？要素1つの列は自明に整列されているとみなせるから，1+1で長さ2の整列された配列ができて，次は2+2で長さ4の整列された配列ができてってのを繰り返せばいける気がする」（実際ソートできる）というのが単純マージソート

func MergeSort(target []int) []int {
	size := 1
	n := len(target)
	arr1 := append(target[:0], append([]int{-1}, target[0:]...)...)
	arr2 := append(target[:0], append([]int{-1}, target[0:]...)...)

	merge := func(size int, from, into *[]int) {
		start := 1
		for start <= n {
			i := start
			j := start + size
			k := start
			iEnd := min(start + size - 1, n)
			jEnd := min(start + size*2 - 1, n)
			for i <= iEnd && j <= jEnd {
				if (*from)[i] <= (*from)[j] {
					(*into)[k] = (*from)[i]
					i += 1
					k += 1
				} else {
					(*into)[k] = (*from)[j]
					j += 1
					k += 1
				}
			}
			for i <= iEnd {
				(*into)[k] = (*from)[i]
				i += 1
				k += 1
			}
			for j <= jEnd {
				(*into)[k] = (*from)[j]
				j += 1
				k += 1
			}
			start = start + size * 2
		}
	}

	for size < n {
		merge(size, &arr1, &arr2)
		merge(size*2, &arr2, &arr1)
		size *= 4
	}
	return arr1[1:]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

トップダウン法

• 単純マージソートは，「マージ」という操作をボトムアップな考え方でソートに用いた
• 逆に，「マージ」という操作をトップダウンなアプローチでソートに用いることもできる
• つまり，整列された列をまず想定して，それを得るためにはどうやって分解すればいいかを考える
• クイックソートと同様に分割統治法を適用する
• クイックソートと違うのは，クイックソートでは分割する操作が重要で，一度分割してしまえば，分割された二つの部分列はそれぞれ独立にソートされるべきだ（部分列同士を統合する必要はない）という態度であったのに対して，マージをトップダウンに適用するマージソートでは，分割する操作にはあまり意味はなくて，分割された部分列同士をどうやって併せるかが重要であるという態度を取っている
• 要素数1の配列は自明に「整列されている」ので，要素数1の配列になるまで分解する途中ではどう分割しても良い（だって統合した結果が整列するように「マージ」するから）
• クイックソートの場合は「分割するときにゆるく整列させている」ので分割が大事．トップダウンなマージソートの場合は「統合するときにゆるく整列させている」

func MergeSort(target []int) []int {
	n := len(target)
	target = append(target[:0], append([]int{-1}, target[0:]...)...)
	sort(&target, 1, n)
	return target[1:]
}

func sort(target *[]int, low, high int) {
	b := make([]int, len(*target))
	if low < high {
		mid := (low + high) / 2
		sort(target, low, mid)
		sort(target, mid + 1, high)
		for i := low; i <= mid; i++ {
			b[i] = (*target)[i]
		}
		for j := mid + 1; j <= high; j++ {
			b[mid + 1 + high - j] = (*target)[j]
		}
		i := low
		j := high
		for k := low; k <= high; k++ {
			if b[i] <= b[j] {
				(*target)[k] = b[i]
				i++
			} else {
				(*target)[k] = b[j]
				j--
			}
		}
	}
}

自然マージソート

• ボトムアップに「マージ」を使うマージソートの一つ
• 単純マージソートでは，自明に整列されている要素数1の列からマージを開始したが，整列対象の列の中に「単調非減少になっている部分列」がある場合には，なにも要素数1の列まで細かいところからマージをするのではなくて，その部分列をマージの入力として扱った方が効率が良さそうじゃん？？？という発想
• 要するに「単調非減少列は（もう整列してるんだから）マージの入力としてまとめて扱えばいいじゃんということ

// いんぷり

リストのマージソート

• 「マージ」は「整列している列同士を併せて，一つの整列している列を作り出す操作」なので，配列だけ弱なくてリストに対してマージソートを考えてもいいでしょう

package main

import (
	"fmt"
)

type Cell struct {
	value int
	next *Cell
}

func Merge(a, b *Cell) *Cell {
	dummy := new(Cell)
	tail := dummy
	for a != nil && b != nil {
		if a.value <= b.value {
			tail.next = a
			tail = a
			a = a.next
		} else {
			tail.next = b
			tail = b
			b = b.next
		}
	}
	if a != nil {
		tail.next = a
	} else {
		tail.next = b
	}
	return dummy.next
}

func main() {
	l1 := prepare(5)
	for i := l1; i != nil; i = i.next {
		fmt.Print(i.value)
	}
	fmt.Println()
	l2 := prepare(5)
	for i := l2; i != nil; i = i.next {
		fmt.Print(i.value)
	}
	fmt.Println()
	merged := Merge(l1, l2)
	for i := merged; i != nil; i = i.next {
		fmt.Print(i.value)
	}
	fmt.Println()
}

func prepare(size int) *Cell {
	input := make([]int, size)
	for i := range input {
		input[i] = i
	}
	ret := new(Cell)
	tail := ret
	for _, ele := range input {
		tail.next = &Cell{value:ele}
		tail = tail.next
	}
	return ret.next
}