# Merge Sort in Ruby

## Overview

Merge is a divide and conquer algorithm for sorting which is generally stable. Its average and worst case performance is `O(n log n)`, which makes it more efficient than Insertion for most sets.

## Concise

``````def merge_sort(a)
return numbers if numbers.length <= 1
m = a.length / 2
p l = a[0...m]
p r = a[m..a.length-1]
p l = merge_sort(l)
p r = merge_sort(r)

merge(l, r)
end

def merge(l, r)
o = []
while l.length > 0 || r.length > 0
if l.length > 0 && r.length > 0
l <= r ? o << l.shift : o << r.shift
elsif l.length > 0
o << l.shift
elsif r.length > 0
o << r.shift
end
end
o
end

a = (0..7).to_a.sort{ rand() - 0.5 }[0..7]
p a

s = merge_sort(a)
p s``````
merge_sort.rb

## Verbose

``````# Merge Sort
#
# Input: A sequence of numbers in any order.
# Output: An ordered sequence from smallest number to largest.
#
def merge_sort(numbers)

# Empty sets and singletons are already sorted.
if numbers.length <= 1
return numbers
end

# Split array in two.
middle = numbers.length / 2
left = numbers[0...middle]
right = numbers[middle..numbers.length-1]
puts left.inspect
puts right.inspect

# Recursively call merge_sort to divide
# array into continually smaller sets.
left = merge_sort(left)
right = merge_sort(right)
puts left.inspect
puts right.inspect

# Merge sets.
merge(left, right)
end

def merge(left, right)
result = []

# As long as there are elements to compare.
while left.length > 0 || right.length > 0

# If there are elements in both sets to compare.
if left.length > 0 && right.length > 0

# Smallest element is added to result.
if left <= right
result << left.shift
else
result << right.shift
end

elsif left.length > 0
result << left.shift
elsif right.length > 0
result << right.shift
end
end

result
end

# Generate array of ten random integers.
unsorted = (0..7).to_a.sort{ rand() - 0.5 }[0..7]
puts unsorted.inspect

# Sort.
sorted = merge_sort(unsorted)
puts sorted.inspect``````
merge_sort_verbose.rb

## Sample Input and Output

``````\$ ruby merge_sort.rb
[5, 6, 7, 1, 4, 3, 2, 0]
[5, 6, 7, 1]
[4, 3, 2, 0]
[5, 6]
[7, 1]




[5, 6]




[1, 7]
[1, 5, 6, 7]
[4, 3]
[2, 0]




[3, 4]




[0, 2]
[0, 2, 3, 4]
[0, 1, 2, 3, 4, 5, 6, 7]``````