# 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[0] <= r[0] ? 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
```

## 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[0] <= right[0]
result << left.shift
else
result << right.shift
end
# Otherwise, add remaining elements.
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
```

## 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]
[5]
[6]
[5, 6]
[7]
[1]
[7]
[1]
[1, 7]
[1, 5, 6, 7]
[4, 3]
[2, 0]
[4]
[3]
[4]
[3]
[3, 4]
[2]
[0]
[2]
[0]
[0, 2]
[0, 2, 3, 4]
[0, 1, 2, 3, 4, 5, 6, 7]
```