merge_sort.rb

class Array

	def merge(ary)
		# どちらかの配列が空になるまで、条件にしたがって配列の先頭をtempにpushしていく。
		a1, a2, temp = self.dup, ary.dup, []
		temp << (a1[0] < a2[0] ? a1.shift : a2.shift) until a1.empty? || a2.empty?
		temp + a1 + a2 # 残ったものはすべてtmepにpush
	end

	def merge_sort
		return self if self.size < 2 # 初期処理。selfのサイズが1以下のときは何もしない

		# selfを2分割し、それぞれをソート(再帰)。その後結果をマージする
		pivot = (self.size - 1).div(2)
		a1 = self[0..pivot].merge_sort
		a2 = self[(pivot + 1)...self.size].merge_sort
		a1.merge(a2)
	end

end

# == main ==

arr = (1..10).to_a.shuffle
p arr            #=> [3, 4, 5, 7, 6, 9, 10, 2, 8, 1]
p arr.merge_sort #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]