-
-
Save jnf/b22825985dda93015c0f to your computer and use it in GitHub Desktop.
Starting ground for mergesort in ruby -- with recursive and iterative solutions.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def mergesort(a) | |
# if the array size is 0|1 then the list is considered sorted, return sorted | |
return a if a.length <= 1 | |
# split the list in half | |
left, right = split_array a | |
# merge sort each half | |
sorted_left = mergesort left | |
sorted_right = mergesort right | |
# combine the sorted halves | |
# combine_recursive(sorted_left, sorted_right) | |
combine_until(sorted_left, sorted_right) | |
end | |
def split_array(a) | |
middle = a.length / 2 | |
return a.take(middle), a.drop(middle) | |
end | |
def combine_until(a, b) | |
result = [] | |
until a.empty? || b.empty? do | |
if a[0] < b[0] | |
result.push a.shift | |
else | |
result.push b.shift | |
end | |
end | |
result + a + b | |
end | |
def combine_recursive(a, b) | |
# puts "a: #{a.inspect} | b: #{b.inspect}" | |
return a if b.empty? | |
return b if a.empty? | |
smallest = a[0] < b[0] ? a.shift : b.shift | |
combine_recursive(a, b).unshift(smallest) | |
end | |
# TEST IT | |
a = [6,23,53,1,2,5,62,61,33,21,14,6,23] | |
puts "ORIGINAL \n" + a.to_s | |
a = a.shuffle | |
a = mergesort(a) | |
puts "AFTER MERGESORT \n" + a.to_s |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Line 33 is my favorite 😍