Skip to content

Instantly share code, notes, and snippets.

@kimhunter
Created October 13, 2011 15:08
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save kimhunter/1284454 to your computer and use it in GitHub Desktop.
Save kimhunter/1284454 to your computer and use it in GitHub Desktop.
Merge sort ruby
#!/usr/bin/env ruby
# 2011-10-10 20:57:53 +1000
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
return a.take(mid), a[mid, a.size-mid]
end
def combine a, b
return b.size.zero? ? a : b if a.first.nil? || b.first.nil?
smallest = a.first <= b.first ? a.shift : b.shift
return combine(a, b).unshift(smallest)
end
a = [6,23,53,1,2,5,62,61,33,21,14,6,23].shuffle
puts "#{merge_sort(a)}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment