RickBacci
7/27/2015 - 9:48 PM

## Merge sort

Merge sort

``````
def merge_sort(array)
return array if array.length < 2
mid   = array.length / 2
left  = merge_sort(array[0, mid])
right = merge_sort(array[mid, array.length-mid])
merge_sorted_arrays left, right
end

def merge_sorted_arrays(array1, array2, merged_array=[])

if array1.empty? || array2.empty?
if array1.empty?
return (merged_array << array2).flatten
else
return (merged_array << array1).flatten
end
end

until array1.empty? || array2.empty?
if array1.first < array2.first
merged_array << array1.shift
else
merged_array << array2.shift
end
end

if array1.empty? && array2.empty?
return merged_array
else
merge_sorted_arrays(array1, array2, merged_array)
end
end

p merge_sorted_arrays([],      [])            # => []
p merge_sorted_arrays([],      [1])           # => [1]
p merge_sorted_arrays([1],     [])            # => [1]
p merge_sorted_arrays([1],     [2])           # => [1, 2]
p merge_sorted_arrays([2],     [1])           # => [1, 2]
p merge_sorted_arrays([1,3],   [2])           # => [1, 2, 3]
p merge_sorted_arrays([2],     [1,3])         # => [1, 2, 3]
p merge_sorted_arrays([1,2,3], [4])           # => [1, 2, 3, 4]
p merge_sorted_arrays([4],     [1,2,3])       # => [1, 2, 3, 4]

p merge_sorted_arrays([]         , [])        # => []
p merge_sorted_arrays([1]        , [])        # => [1]
p merge_sorted_arrays([2]        , [1])       # => [1, 2]
p merge_sorted_arrays([1,2,3]    , [])        # => [1, 2, 3]
p merge_sorted_arrays([4]        , [1,2,3])   # => [1, 2, 3, 4]
p merge_sorted_arrays([1,3]      , [2,4,5])   # => [1, 2, 3, 4, 5]
p merge_sorted_arrays([1,2,3,4,6], [5])       # => [1, 2, 3, 4, 5, 6]
p merge_sorted_arrays([1,3,4,6,7], [2,5])     # => [1, 2, 3, 4, 5, 6, 7]
p merge_sorted_arrays([2,5,6,8]  , [1,3,4,7]) # => [1, 2, 3, 4, 5, 6, 7, 8]
p merge_sorted_arrays([2,4,6,7,8], [1,3,5,9]) # => [1, 2, 3, 4, 5, 6, 7, 8, 9]
``````