# アルゴリズム | マージソート

マージソート

#### 内容

データを分割し、それぞれをソート後、結果をマージする。

#### コード

merge_sort.rb

```# encoding: utf-8

class Array
def merge_sort
s = self.size
return self if s == 1
lesses = self.pop(s >> 1)
merge_for_sort(self.merge_sort, lesses.merge_sort)
end

private
def merge_for_sort(lesses, largers)
less_index = 0
lesses_size = lesses.size
ret = []
total = 0
largers.each do |large|
is_set_large = false
(less_index..lesses_size - 1).each do |j|
less = lesses[j]
if large < less
ret << large
is_set_large = true
total += 1
break
else
ret << less
less_index += 1
total += 1
end
end
unless is_set_large
ret << large
total += 1
end
end

unless less_index == lesses_size
(less_index..(lesses_size- 1)).each do |k|
ret[total] = lesses[k]
total += 1
end
end
ret
end
end
```

#### テストコード

merge_sort_spec.rb

```# encoding: utf-8
require_relative "../merge_sort"

describe Array do
cases = [
{
input_ary: [5,4,3,2,1],
expected: [1,2,3,4,5]
},
{
input_ary: [1,2,3,4,5],
expected: [1,2,3,4,5]
},
{
input_ary: [1,4,3,2,5],
expected: [1,2,3,4,5]
},
{
input_ary: [2,4,3,5,1],
expected: [1,2,3,4,5]
},
{
input_ary: [3,4,5,2,1],
expected: [1,2,3,4,5]
}
]

cases.each do |c|
it "#merge_sort" do
actual = c[:input_ary].merge_sort
expect(actual).to eq(c[:expected])
end
end
end
```