While playing around with stable sorting I implemented Mergesort.

```
class Array
def mergesort(&cmp)
if cmp == nil
cmp = lambda { |a, b| a <=> b }
end
if size <= 1
self.dup
else
halves = split.map{ |half|
half.mergesort(&cmp)
}
merge(*halves, &cmp)
end
end
protected
def split
n = (length / 2).floor - 1
[self[0..n], self[n+1..-1]]
end
def merge(first, second, &predicate)
result = []
until first.empty? || second.empty?
if predicate.call(first.first, second.first) <= 0
result << first.shift
else
result << second.shift
end
end
result.concat(first).concat(second)
end
end
```

It is not suitable for productive use as it’s quite slow. It’s about ten times slower than the stable_sort method from my another post. A little benchmark sorting an array of 2,000,000 random integers:

```
user system total real
Original Sort 0.630000 0.010000 0.640000 ( 0.639860)
Stable Sort 12.780000 0.700000 13.480000 ( 13.477982)
Mergesort 109.170000 13.420000 122.590000 (122.617323)
```