マージソート

Google先生「Bubble sortてww」って言われたので計算量:O(NlogN)のマージソート．聞いたことだけある．なんなの，難しい．
ミソなのは，"あらかじめ昇順に並んでいる配列同士を昇順にまとめる"で，1回の比較で1つの値を入れていけるのが強いんかな．たぶん．

1.作る

original = (1..8).to_a.shuffle
>[8, 5, 6, 3, 7, 4, 2, 1]

2.バラバラにする．

def mydivider(arr)
	divided = []
	arr.each do |i|
		arr = []
		arr << i
		divided << arr
	end
	return divided
end

divided = mydivider(original)
>[[8], [5], [6], [3], [7], [4], [2], [1]]

3.マージのサンプル作る

#Merge two arrays in ascending.
#The two must be sorted in ascending.
def mymerger(left,right)
	merged = []
	i=0
	j=0

	while(left[i]!=nil || right[j]!=nil)
		if(left[i] == nil)
			merged << right[j]
			j += 1
		elsif(right[j] == nil)
			merged << left[i]
			i += 1
		elsif(left[i] < right[j])
			merged << left[i]
			i += 1
		elsif(left[i] > right[j])
			merged << right[j]
			j += 1
		end
	end

	return merged
end

mymerger([2,3],[1,4])
>[1,2,3,4]

これはひどい．

4.全部通す

def mergesort(arr)
	#dividing
	divided = mydivider(arr)
	p divided

	#merging
	while(divided.length != 1) do
		for i in 0..divided.length-1 do
			if(divided[i+1] != nil)
				divided[i] = mymerger(divided[i],divided[i+1])
				divided.delete_at(i+1)
			end
		end
		p divided
	end

end

>[[8], [5], [6], [3], [7], [4], [2], [1]]
>[[5, 8], [3, 6], [4, 7], [1, 2]]
>[[3, 5, 6, 8], [1, 2, 4, 7]]
>[[1, 2, 3, 4, 5, 6, 7, 8]]

要素数が2の倍数なら問題ないけど，10なら変だ．

[[10], [1], [5], [6], [2], [8], [4], [7], [9], [3]]
[[1, 10], [5, 6], [2, 8], [4, 7], [3, 9]]
[[1, 5, 6, 10], [2, 4, 7, 8], [3, 9]]
[[1, 2, 4, 5, 6, 7, 8, 10], [3, 9]]このへん
[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]

これは「ちょうど真ん中」を意識できてないから計算量の仕組み変わりそう．