# 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

``` 1def merge_sort(a)
2  return numbers if numbers.length <= 1
3
4  m = a.length / 2
5  p l = a[0...m]
6  p r = a[m..a.length-1]
7
8  p l = merge_sort(l)
9  p r = merge_sort(r)
10
11  merge(l, r)
12end
13
14def merge(l, r)
15  o = []
16  while l.length > 0 || r.length > 0
17    if l.length > 0 && r.length > 0
18      l <= r ? o << l.shift : o << r.shift
19    elsif l.length > 0
20      o << l.shift
21    elsif r.length > 0
22      o << r.shift
23    end
24  end
25  o
26end
27
28a = (0..7).to_a.sort{ rand() - 0.5 }[0..7]
29p a
30
31s = merge_sort(a)
32p s```

## Verbose

``` 1# Merge Sort
2#
3# Input: A sequence of numbers in any order
4# Output: An ordered sequence from smallest number to largest
5#
6def merge_sort(numbers)
7
8  # Empty sets and singletons are already sorted
9  if numbers.length <= 1
10    return numbers
11  end
12
13  # Split array in two
14  middle = numbers.length / 2
15  left = numbers[0...middle]
16  right = numbers[middle..numbers.length-1]
17
18  puts left.inspect
19  puts right.inspect
20
21  # Recursively call merge_sort to divide
22  # array into continually smaller sets
23  left = merge_sort(left)
24  right = merge_sort(right)
25
26  puts left.inspect
27  puts right.inspect
28
29  # Merge sets
30  merge(left, right)
31end
32
33def merge(left, right)
34  result = []
35
36  # As long as there are elements to compare
37  while left.length > 0 || right.length > 0
38
39    # If there are elements in both sets to compare
40    if left.length > 0 && right.length > 0
41
42      # Smallest element is added to result
43      if left <= right
44        result << left.shift
45      else
46        result << right.shift
47      end
48
49    # Otherwise, add remaining elements
50    elsif left.length > 0
51      result << left.shift
52    elsif right.length > 0
53      result << right.shift
54    end
55  end
56
57  result
58end
59
60# Generate array of ten random integers
61unsorted = (0..7).to_a.sort{ rand() - 0.5 }[0..7]
62puts unsorted.inspect
63
64# Sort
65sorted = merge_sort(unsorted)
66puts sorted.inspect
```

## Sample Input & Output

``` 1\$ ruby merge_sort.rb
2[5, 6, 7, 1, 4, 3, 2, 0]
3[5, 6, 7, 1]
4[4, 3, 2, 0]
5[5, 6]
6[7, 1]
7
8
9
10
11[5, 6]
12
13
14
15
16[1, 7]
17[1, 5, 6, 7]
18[4, 3]
19[2, 0]
20
21
22
23
24[3, 4]
25
26
27
28
29[0, 2]
30[0, 2, 3, 4]
31[0, 1, 2, 3, 4, 5, 6, 7]```