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[0] <= r[0] ? 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[0] <= right[0]
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[5]
 8[6]
 9[5]
10[6]
11[5, 6]
12[7]
13[1]
14[7]
15[1]
16[1, 7]
17[1, 5, 6, 7]
18[4, 3]
19[2, 0]
20[4]
21[3]
22[4]
23[3]
24[3, 4]
25[2]
26[0]
27[2]
28[0]
29[0, 2]
30[0, 2, 3, 4]
31[0, 1, 2, 3, 4, 5, 6, 7]

Further Reading