Skip to content

Instantly share code, notes, and snippets.

@tharrington
Created December 19, 2013 21:52
Show Gist options
  • Save tharrington/8046887 to your computer and use it in GitHub Desktop.
Save tharrington/8046887 to your computer and use it in GitHub Desktop.
Merge sort implementation in Ruby
def merge_sort(a)
return a if a.size <= 1
l, r = split_array(a)
result = combine(merge_sort(l), merge_sort(r))
end
def split_array a
mid = (a.size / 2).round
[a.take(mid), a.drop(mid)]
end
def combine a, b
return b.empty? ? a : b if a.empty? || b.empty?
smallest = a.first <= b.first ? a.shift : b.shift
combine(a, b).unshift(smallest)
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment